Particle competition for complex network community detection

Temporal Network Pattern Identification by Community Modelling

Temporal network mining tasks are usually hard problems. This is because we need to face not only a large amount of data but also its non-stationary nature. In this paper, we propose a method for temporal network pattern representation and pattern change detection following the reductionist approach. The main idea is to model each stable (durable) state of a given temporal network as a community in a sampled static network and the temporal state change is represented by the transition from one community to another. For this purpose, a reduced static single-layer network, called a target network, is constructed by sampling and rearranging the original temporal network. Our approach provides a general way not only for temporal networks but also for data stream mining in topological space. Simulation results on artificial and real temporal networks show that the proposed method can group different temporal states into different communities with a very reduced amount of sampled nodes.

A novel complex network link prediction framework via combining mutual information with local naive Bayes

As an important research direction of complex networks and data mining, link prediction has attracted more and more scholars' attention. In the early research, the common neighbor is regarded as a key factor affecting the formation of links, and the prediction accuracy is improved by distinguishing the contribution of each common neighbor more accurately. However, there is a drawback that the interactions between common neighbors are ignored. Actually, it is not just the interactions between common neighbors, but all the interactions between neighbor sets contribute to the formation of links. Therefore, the core of this work is how to better quantify and balance the contributions caused by common neighbors and the interactions between neighbor sets, so as to improve the accuracy of prediction. Specifically, local naive Bayes and mutual information are utilized to quantify the influence of the two aspects, and an adjustable parameter is introduced to distinguish the two contributions in this paper. Subsequently, the mutual information-based local naive Bayes algorithm is proposed. Simulation experiments are conducted on 5 datasets belonging to different fields, and 9 indexes are utilized for comparison. Numerical simulation results verify the effectiveness of the proposed algorithm for improving link prediction performance.

Mean-field analysis of directed modular networks

We considered a modular network with a binomial degree distribution and related the analytical relationships of the network properties (modularity, average clustering coefficient, and small-worldness) with structural parameters that define the network, i.e., number of nodes, number of modules, average node degree, and ratio of intra-modular to total connections. Even though modular networks are universally found in real-world systems and are consequently of broad interest in complex network science, the relationship between network properties and structural parameters has not yet been formulated. Here, we show that a series of equations for predicting the network properties can be related using a mean-field connectivity matrix that is defined on the basis of the structural parameters in the network generation algorithm. The theoretical results are then compared with values calculated numerically using the original connectivity matrix and are found to agree well, except when the connections between modules are sparse. Representation of the structure of the network using simple parameters is expected to be conducive for elucidating the structure-dynamics relationship.

Network Unfolding Map by Vertex-Edge Dynamics Modeling

The emergence of collective dynamics in neural networks is a mechanism of the animal and human brain for information processing. In this paper, we develop a computational technique using distributed processing elements in a complex network, which are called particles, to solve semisupervised learning problems. Three actions govern the particles' dynamics: generation, walking, and absorption. Labeled vertices generate new particles that compete against rival particles for edge domination. Active particles randomly walk in the network until they are absorbed by either a rival vertex or an edge currently dominated by rival particles. The result from the model evolution consists of sets of edges arranged by the label dominance. Each set tends to form a connected subnetwork to represent a data class. Although the intrinsic dynamics of the model is a stochastic one, we prove that there exists a deterministic version with largely reduced computational complexity; specifically, with linear growth. Furthermore, the edge domination process corresponds to an unfolding map in such way that edges "stretch" and "shrink" according to the vertex-edge dynamics. Consequently, the unfolding effect summarizes the relevant relationships between vertices and the uncovered data classes. The proposed model captures important details of connectivity patterns over the vertex-edge dynamics evolution, in contrast to the previous approaches, which focused on only vertex or only edge dynamics. Computer simulations reveal that the new model can identify nonlinear features in both real and artificial data, including boundaries between distinct classes and overlapping structures of data.

Partially labeled data stream classification with the semi-supervised K-associated graph

Regular data classification techniques are based mainly on two strong assumptions: (1) the existence of a reasonably large labeled set of data to be used in training; and (2) future input data instances conform to the distribution of the training set, i.e. data distribution is stationary along time. However, in the case of data stream classification, both of the aforementioned assumptions are difficult to satisfy. In this paper, we present a graph-based semi-supervised approach that extends the static classifier based on the K-associated Optimal Graph to perform online semi-supervised classification tasks. In order to learn from labeled and unlabeled patterns, here we adapt the optimal graph construction to simultaneously spread the labels in the training set. The sparse, disconnected nature of the proposed graph structure gives flexibility to cope with non-stationary classification. Experimental comparison between the proposed method and three state-of-the-art ensemble classification methods is provided and promising results have been obtained.

Network-based stochastic semisupervised learning

Semisupervised learning is a machine learning approach that is able to employ both labeled and unlabeled samples in the training process. In this paper, we propose a semisupervised data classification model based on a combined random-preferential walk of particles in a network (graph) constructed from the input dataset. The particles of the same class cooperate among themselves, while the particles of different classes compete with each other to propagate class labels to the whole network. A rigorous model definition is provided via a nonlinear stochastic dynamical system and a mathematical analysis of its behavior is carried out. A numerical validation presented in this paper confirms the theoretical predictions. An interesting feature brought by the competitive-cooperative mechanism is that the proposed model can achieve good classification rates while exhibiting low computational complexity order in comparison to other network-based semisupervised algorithms. Computer simulations conducted on synthetic and real-world datasets reveal the effectiveness of the model.

Stochastic competitive learning in complex networks

Competitive learning is an important machine learning approach which is widely employed in artificial neural networks. In this paper, we present a rigorous definition of a new type of competitive learning scheme realized on large-scale networks. The model consists of several particles walking within the network and competing with each other to occupy as many nodes as possible, while attempting to reject intruder particles. The particle's walking rule is composed of a stochastic combination of random and preferential movements. The model has been applied to solve community detection and data clustering problems. Computer simulations reveal that the proposed technique presents high precision of community and cluster detections, as well as low computational complexity. Moreover, we have developed an efficient method for estimating the most likely number of clusters by using an evaluator index that monitors the information generated by the competition process itself. We hope this paper will provide an alternative way to the study of competitive learning..