Identification of network modules by optimization of ratio association

MOPIO: A Multi-Objective Pigeon-Inspired Optimization Algorithm for Community Detection

Community detection is a hot research direction of network science, which is of great importance to complex system analysis. Therefore, many community detection methods have been developed. Among them, evolutionary computation based ones with a single-objective function are promising in either benchmark or real data sets. However, they also encounter resolution limit problem in several scenarios. In this paper, a Multi-Objective Pigeon-Inspired Optimization (MOPIO) method is proposed for community detection with Negative Ratio Association (NRA) and Ratio Cut (RC) as its objective functions. In MOPIO, the genetic operator is used to redefine the representation and updating of pigeons. In each iteration, NRA and RC are calculated for each pigeon, and Pareto sorting scheme is utilized to judge non-dominated solutions for later crossover. A crossover strategy based on global and personal bests is designed, in which a compensation coefficient is developed to stably complete the work transition between the map and compass operator, and the landmark operator. When termination criteria were met, a leader selection strategy is employed to determine the final result from the optimal solution set. Comparison experiments of MOPIO, with MOPSO, MOGA-Net, Meme-Net and FN, are performed on real-world networks, and results indicate that MOPIO has better performance in terms of Normalized Mutual information and Adjusted Rand Index.

A Consensus Community-Based Particle Swarm Optimization for Dynamic Community Detection

The community detection in dynamic networks is essential for important applications such as social network analysis. Such detection requires simultaneous maximization of the clustering accuracy at the current time step while minimization of the clustering drift between two successive time steps. In most situations, such objectives are often in conflict with each other. This article proposes the concept of consensus community. Knowledge from the previous step is obtained by extracting the intrapopulation consensus communities from the optimal population of the previous step. Subsequently, the intrapopulation consensus communities of the previous step obtained is voted by the population of the current time step during the evolutionary process. A subset of the consensus communities, which receives a high support rate, will be recognized as the interpopulation consensus communities of the previous and current steps. Interpopulation consensus communities are the knowledge that can be transferred from the previous to the current step. The population of the current time step can evolve toward the direction similar to the population in the previous time step by retaining such interpopulation consensus community during the evolutionary process. Community structure is subjected to evaluation, update, and mutation events, which are directed by using interpopulation consensus community information during the evolutionary process. The experimental results over many artificial and real-world dynamic networks illustrate that the proposed method produces more accurate and robust results than those of the state-of-the-art approaches.

Balanced Centrality of Networks

There is an age-old question in all branches of network analysis. What makes an actor in a network important, courted, or sought? Both Crossley and Bonacich contend that rather than its intrinsic wealth or value, an actor's status lies in the structures of its interactions with other actors. Since pairwise relation data in a network can be stored in a two-dimensional array or matrix, graph theory and linear algebra lend themselves as great tools to gauge the centrality (interpreted as importance, power, or popularity, depending on the purpose of the network) of each actor. We express known and new centralities in terms of only two matrices associated with the network. We show that derivations of these expressions can be handled exclusively through the main eigenvectors (not orthogonal to the all-one vector) associated with the adjacency matrix. We also propose a centrality vector (SWIPD) which is a linear combination of the square, walk, power, and degree centrality vectors with weightings of the various centralities depending on the purpose of the network. By comparing actors' scores for various weightings, a clear understanding of which actors are most central is obtained. Moreover, for threshold networks, the (SWIPD) measure turns out to be independent of the weightings.

Non-negative sparse autoencoder neural networks for the detection of overlapping, hierarchical communities in networked datasets

We propose the first use of a non-negative sparse autoencoder (NNSAE) neural network for community structure detection in complex networks. The NNSAE learns a compressed representation of a set of fixed-length, weighted random walks over the network, and communities are detected as subsets of network nodes corresponding to non-negligible elements of the basis vectors of this compression. The NNSAE model is efficient and online. When utilized for community structure detection, it is able to uncover potentially overlapping and hierarchical community structure in large networks.

Network community-detection enhancement by proper weighting

In this paper, we show how proper assignment of weights to the edges of a complex network can enhance the detection of communities and how it can circumvent the resolution limit and the extreme degeneracy problems associated with modularity. Our general weighting scheme takes advantage of graph theoretic measures and it introduces two heuristics for tuning its parameters. We use this weighting as a preprocessing step for the greedy modularity optimization algorithm of Newman to improve its performance. The result of the experiments of our approach on computer-generated and real-world data networks confirm that the proposed approach not only mitigates the problems of modularity but also improves the modularity optimization.

Partitioning networks into clusters and residuals with average association

We investigate the problem of detecting clusters exhibiting higher-than-average internal connectivity in networks of interacting systems. We show how the average association objective formulated in the context of spectral graph clustering leads naturally to a clustering strategy where each system is assigned to at most one cluster. A residual set is formed of the systems that are not members of any cluster. Maximization of the average association objective leads to a discrete optimization problem, which is difficult to solve, but a relaxed version can be solved using an eigendecomposition of the connectivity matrix. A simple approach to extracting clusters from a relaxed solution is described and developed by applying a variance maximizing solution to the relaxed solution, which leads to a method with increased accuracy and sensitivity. Numerical studies of theoretical connectivity models and of synchronization clusters in a lattice of coupled Lorenz oscillators are conducted to show the efficiency of the proposed approach. The method is applied to an experimentally obtained human resting state functional magnetic resonance imaging dataset and the results are discussed.

Kernel-Granger causality and the analysis of dynamical networks

We propose a method of analysis of dynamical networks based on a recent measure of Granger causality between time series, based on kernel methods. The generalization of kernel-Granger causality to the multivariate case, here presented, shares the following features with the bivariate measures: (i) the nonlinearity of the regression model can be controlled by choosing the kernel function and (ii) the problem of false causalities, arising as the complexity of the model increases, is addressed by a selection strategy of the eigenvectors of a reduced Gram matrix whose range represents the additional features due to the second time series. Moreover, there is no a priori assumption that the network must be a directed acyclic graph. We apply the proposed approach to a network of chaotic maps and to a simulated genetic regulatory network: it is shown that the underlying topology of the network can be reconstructed from time series of node's dynamics, provided that a sufficient number of samples is available. Considering a linear dynamical network, built by preferential attachment scheme, we show that for limited data use of the bivariate Granger causality is a better choice than methods using L1 minimization. Finally we consider real expression data from HeLa cells, 94 genes and 48 time points. The analysis of static correlations between genes reveals two modules corresponding to well-known transcription factors; Granger analysis puts in evidence 19 causal relationships, all involving genes related to tumor development.

Quantitative function for community detection

We propose a quantitative function for community partition -- i.e., modularity density or D value. We demonstrate that this quantitative function is superior to the widely used modularity Q and also prove its equivalence with the objective function of the kernel k means. Both theoretical and numerical results show that optimizing the new criterion not only can resolve detailed modules that existing approaches cannot achieve, but also can correctly identify the number of communities.

Modularity and community detection in bipartite networks

The modularity of a network quantifies the extent, relative to a null model network, to which vertices cluster into community groups. We define a null model appropriate for bipartite networks, and use it to define a bipartite modularity. The bipartite modularity is presented in terms of a modularity matrix B; some key properties of the eigenspectrum of B are identified and used to describe an algorithm for identifying modules in bipartite networks. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. We apply the algorithm to real-world network data, showing that the algorithm successfully identifies the modular structure of bipartite networks.