Detecting community structures and analyzing temporal evolution in dynamic networks are challenging tasks to explore the inherent characteristics of the complex networks. In this paper, we propose a semi-supervised evolutionary clustering model based on symmetric nonnegative matrix factorization to detect communities in dynamic networks, named sEC-SNMF. We use the results of community partition at the previous time step as the priori information to modify the current network topology, then smooth-out the evolution of the communities and reduce the impact of noise. Furthermore, we introduce a community transition probability matrix to track and analyze the temporal evolutions. Different from previous algorithms, our approach does not need to know the number of communities in advance and can deal with the situation in which the number of communities and nodes varies over time. Extensive experiments on synthetic datasets demonstrate that the proposed method is competitive and has a superior performance.

Adaptive and flexible network control technology is considered essential for efficient network resource utilization. Moreover, such technology is becoming a key to cost-effectively meet diverse service requirements and accommodate heavier traffic with limited network resources; demands that conventional static operation cannot satisfy. To address this issue, we previously studied dynamic network control technology for large-capacity network services including on-demand broad bandwidth provisioning services and layer-one VPN. Our previous study introduced a simple weighting function for achieving fairness in terms of path length and proposed two dynamic Make Before Break Routing algorithms for reducing blocking probability. These algorithms enhance network utilization by rerouting existing paths to alternative routes while completely avoiding disruption for highly reliable services. However, the impact of this avoidance of service disruption on blocking probability has not been clarified. In this paper, we propose modified versions of the algorithms that enhance network utilization while slightly increasing disruption by rerouting, which enable us to elucidate the effectiveness of hitless rerouting. We also provide extensive evaluations including a comparison of original and modified algorithms. Numerical examples demonstrate that they achieve not only a high degree of fairness but also low service blocking probability. Hitless rerouting is achieved with a small increase in blocking probability.

Many kinds of data can be represented as a network or graph. It is crucial to infer the latent structure underlying such a network and to predict unobserved links in the network. Mixed Membership Stochastic Blockmodel (MMSB) is a promising model for network data. Latent variables and unknown parameters in MMSB have been estimated through Bayesian inference with the entire network; however, it is important to estimate them online for evolving networks. In this paper, we first develop online inference methods for MMSB through sequential Monte Carlo methods, also known as particle filters. We then extend them for time-evolving networks, taking into account the temporal dependency of the network structure. We demonstrate through experiments that the time-dependent particle filter outperformed several baselines in terms of prediction performance in an online condition.

In the literature, two connectivity-based distributed clustering schemes exist: CDC (Connectivity-based Distributed node Clustering scheme) and SDC (SCM-based Distributed Clustering). While CDC and SDC have mechanisms for maintaining clusters against nodes joining and leaving, neither method assumes that frequent changes occur in the network topology. In this paper, we propose a lightweight distributed clustering method that we term SBDC (Schelling-Based Distributed Clustering) since this scheme is derived from Schelling's model – a popular segregation model in sociology. We evaluate the effectiveness of the proposed SBDC in an environment where frequent changes arise in the network topology. Our simulation results show that SBDC outperforms CDC and SDC under frequent changes in network topology caused by high node mobility.

A self-stabilizing protocol is a protocol that achieves its intended behavior regardless of the initial configuration (i.e., global state). Thus, a self-stabilizing protocol is adaptive to any number and any type of topology changes of networks: after the last topology change occurs, the protocol starts to converge to its intended behavior. This advantage makes self-stabilizing protocols extremely attractive for designing highly dependable distributed systems on dynamic networks. While conventional self-stabilizing protocols require that the networks remain static during convergence to the intended behaviors, some recent works undertook the challenge of realizing self-stabilization in dynamic networks with frequent topology changes. This paper introduces some of the challenges as a new direction of research in self-stabilization.

Mobile-agent-based distributed computing is one of the most promising paradigms to support autonomic computing in a large-scale of distributed system with dynamics and diversity: mobile agents traverse the distributed system and carry out a sophisticated task at each node adaptively. In mobile-agent-based systems, a larger number of agents generally require shorter time to complete the whole task but consume more resources (e.g., processing power and network bandwidth). Therefore, it is indispensable to keep an appropriate number of agents for the application on the mobile-agent-based system. This paper considers the mobile agent population control problem in dynamic networks: it requires adjusting the number of agents to a constant fraction of the current network size. This paper proposes algorithms inspired by the single species population model, which is a well-known population ecology model. These two algorithms are different in knowledge of networks each node requires. The first algorithm requires global information at each node, while the second algorithm requires only the local information. This paper shows by simulations that the both algorithms realize self-adaptation of mobile agent population in dynamic networks, but the second algorithm attains slightly lower accuracy than the first one.

In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.

This paper presents a new decoding framework for large vocabulary continuous speech recognition that can handle a static search network dynamically. Generally, a static network decoder can use a search space that is globally optimized in advance, and therefore it can run at high speed during decoding. However, its large memory requirement due to the large network size or the spatial complexity of the optimization algorithm often makes it impractical. Our new one-pass semi-dynamic network decoding scheme aims at incorporating such an optimized search network with memory efficiency, but without losing speed. In this framework, a complete search network is organized on the basis of self-structuring subnetworks and is nearly minimized using a modified tail-sharing algorithm. While the decoder runs, it caches subnetworks needed for decoding in memory, whereas static network decoders keep the complete network in memory. The subnetwork caching model is controlled by two levels of caches: local cache obtained by subnetwork caching operations and global cache obtained by subnetwork preloading operations. The model can also be controlled adaptively by using subnetwork profiling operations. Furthermore, it is made simple and fast with compactly designed self-structuring subnetworks. Experimental results on a 25 k-word Korean broadcast news transcription task show that the semi-dynamic decoder can run almost as fast as an equivalent static network decoder under various memory configurations by using the subnetwork caching model.