Modular networks with hierarchical organization: The dynamical implications of complex structure

Several networks occurring in real life have modular structures that are arranged in a hierarchical fashion. In this paper, we have proposed a model for such networks, using a stochastic generation method. Using this model we show that, the scaling relation between the clustering and degree of the nodes is not a necessary property of hierarchical modular networks, as had previously been suggested on the basis of a deterministically constructed model. We also look at dynamics on such networks, in particular, the stability of equilibria of network dynamics and of synchronized activity in the network. For both of these, we find that, increasing modularity or the number of hierarchical levels tends to increase the probability of instability. As both hierarchy and modularity are seen in natural systems, which necessarily have to be robust against environmental fluctuations, we conclude that additional constraints are necessary for the emergence of hierarchical structure, similar to the occurrence of modularity through multi-constraint optimization as shown by us previously.      

A modular attachment mechanism for software network evolution

A modular attachment mechanism of software network evolution is presented in this paper. Compared with the previous models, our treatment of object-oriented software system as a network of modularity is inherently more realistic. To acquire incoming and outgoing links in directed networks when new nodes attach to the existing network, a new definition of asymmetric probabilities is given. Based on this, modular attachment instead of single node attachment in the previous models is then adopted. The proposed mechanism is demonstrated to be able to generate networks with features of power-law, small-world, and modularity, which represents more realistic properties of actual software networks. This work therefore contributes to a more accurate understanding of the evolutionary mechanism of software systems. What is more, explorations of the effects of various software development principles on the structure of software systems have been carried out, which are expected to be beneficial to the software engineering practices.     

Comparison of methods for the detection of node group membership in bipartite networks

Most real-world networks considered in the literature have a modular structure. Analysis of these real-world networks often are performed under the assumption that there is only one type of node. However, social and biochemical systems are often bipartite networks, meaning that there are two exclusive sets of nodes, and that edges run exclusively between nodes belonging to different sets. Here we address the issue of module detection in bipartite networks by comparing the performance of two classes of group identification methods – modularity maximization and clique percolation – on an ensemble of modular random bipartite networks. We find that the modularity maximization methods are able to reliably detect the modular bipartite structure, and that, under some conditions, the simulated annealing method outperforms the spectral decomposition method. We also find that the clique percolation methods are not capable of reliably detecting the modular bipartite structure of the bipartite model networks considered.     

LPA-MNI: An Improved Label Propagation Algorithm Based on Modularity and Node Importance for Community Detection

Community detection is of great significance in understanding the structure of the network. Label propagation algorithm (LPA) is a classical and effective method, but it has the problems of randomness and instability. An improved label propagation algorithm named LPA-MNI is proposed in this study by combining the modularity function and node importance with the original LPA. LPA-MNI first identify the initial communities according to the value of modularity. Subsequently, the label propagation is used to cluster the remaining nodes that have not been assigned to initial communities. Meanwhile, node importance is used to improve the node order of label updating and the mechanism of label selecting when multiple labels are contained by the maximum number of nodes. Extensive experiments are performed on twelve real-world networks and eight groups of synthetic networks, and the results show that LPA-MNI has better accuracy, higher modularity, and more reasonable community numbers when compared with other six algorithms. In addition, LPA-MNI is shown to be more robust than the traditional LPA algorithm.     

Detecting local community structures in complex networks based on local degree central nodes

Detecting local communities in real-world graphs such as large social networks, web graphs, and biological networks has received a great deal of attention because obtaining complete information from a large network is still difficult and unrealistic nowadays. In this paper, we define the term local degree central node whose degree is greater than or equal to the degree of its neighbor nodes. A new method based on the local degree central node to detect the local community is proposed. In our method, the local community is not discovered from the given starting node, but from the local degree central node that is associated with the given starting node. Experiments show that the local central nodes are key nodes of communities in complex networks and the local communities detected by our method have high accuracy. Our algorithm can discover local communities accurately for more nodes and is an effective method to explore community structures of large networks.     

Identifying Functional Modules in Complex Networks

In this paper, we propose a new method that enables us to detect and describe the functional modules in complex networks. Using the proposed method, we can classify the nodes of networks into different modules according to their pattern of intra- and extra-module links. We use our method to analyze the modular structures of the ER random networks. We find that different modules of networks have different structure properties, such as the clustering coefficient. Moreover, at the same time, many nodes of networks participate different modules. Remarkably, we find that in the ER random networks, when the probability p is small, different modules or different roles of nodes can be Mentified by different regions in the c-p parameter space.     

EAMCD: an efficient algorithm based on minimum coupling distance for community identification in complex networks

Community structure is an important feature in many real-world networks, which can help us understand structure and function in complex networks better. In recent years, there have been many algorithms proposed to detect community structure in complex networks. In this paper, we try to detect potential community beams whose link strengths are greater than surrounding links and propose the minimum coupling distance (MCD) between community beams. Based on MCD, we put forward an optimization heuristic algorithm (EAMCD) for modularity density function to welded these community beams into community frames which are seen as a core part of community. Using the principle of random walk, we regard the remaining nodes into the community frame to form a community. At last, we merge several small community frame fragments using local greedy strategy for the modularity density general function. Real-world and synthetic networks are used to demonstrate the effectiveness of our algorithm in detecting communities in complex networks.     

蛋白质相互作用网络特征的理论再现

无标度性、小世界性、功能模块结构及度负关联性是大量生物网络共同的特征. 为了理解生物网络无标度性、小世界性和度负关联性的形成机制, 研究者已经提出了各种各样基于复制和变异的网络增长模型. 在本文中,我们从生物学的角度通过引入偏爱小复制原则及变异和非均匀的异源二聚作用构建了一个简单的蛋白质相互作用网络演化模型.数值模拟结果表明,该演化模型几乎可以再现现在实测结果所公认的蛋白质相互作用网络的性质：无标度性、小世界性、度负关联性和功能模块结构. 我们的演化模型对理解蛋白质相互作用网络演化过程中的可能机制提供了一定的帮助. 关键词： 蛋白质相互作用网络 偏爱小 非均匀的异源二聚作用 功能模块结构     

Planar unclustered scale-free graphs as models for technological and biological networks

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases — usually associated with topological restrictions — their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular several families of technological and biological networks, and in the design of new practical communication algorithms in relation to their dynamical processes. They can also help understanding the underlying mechanisms that have produced their particular structure.     

Detection of node group membership in networks with group overlap

Most networks found in social and biochemical systems have modular structures. An important question prompted by the modularity of these networks is whether nodes can be said to belong to a single group. If they cannot, we would need to consider the role of “overlapping communities.” Despite some efforts in this direction, the problem of detecting overlapping groups remains unsolved because there is neither a formal definition of overlapping community, nor an ensemble of networks with which to test the performance of group detection algorithms when nodes can belong to more than one group. Here, we introduce an ensemble of networks with overlapping groups. We then apply three group identification methods – modularity maximization, k-clique percolation, and modularity-landscape surveying – to these networks. We find that the modularity-landscape surveying method is the only one able to detect heterogeneities in node memberships, and that those heterogeneities are only detectable when the overlap is small. Surprisingly, we find that the k-clique percolation method is unable to detect node membership for the overlapping case.     

Community structure and modularity in networks of correlated brain activity

Functional connectivity patterns derived from neuroimaging data may be represented as graphs or networks, with individual image voxels or anatomically-defined structures representing the nodes, and a measure of correlation between the responses in each pair of nodes determining the edges. This explicit network representation allows network-analysis approaches to be applied to the characterization of functional connections within the brain. Much recent research in complex networks has focused on methods to identify community structure, i.e. cohesive clusters of strongly interconnected nodes. One class of such algorithms determines a partition of a network into 'sub-networks' based on the optimization of a modularity parameter, thus also providing a measure of the degree of segregation versus integration in the full network. Here, we demonstrate that a community structure algorithm based on the maximization of modularity, applied to a functional connectivity network calculated from the responses to acute fluoxetine challenge in the rat, can identify communities whose distributions correspond to anatomically meaningful structures and include compelling functional subdivisions in the brain. We also discuss the biological interpretation of the modularity parameter in terms of segregation and integration of brain function.     

Link prediction in complex networks via modularity-based belief propagation

Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes' attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes' similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recovers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.     

Network robustness and fragility: percolation on random graphs

Recent work on the Internet, social networks, and the power grid has addressed the resilience of these networks to either random or targeted deletion of network nodes or links. Such deletions include, for example, the failure of Internet routers or power transmission lines. Percolation models on random graphs provide a simple representation of this process but have typically been limited to graphs with Poisson degree distribution at their vertices. Such graphs are quite unlike real-world networks, which often possess power-law or other highly skewed degree distributions. In this paper we study percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolation, bond percolation, and models in which occupation probabilities depend on vertex degree. We discuss the application of our theory to the understanding of network resilience.     

Refinement of the community detection performance by weighted relationship coupling

The complexity of many community detection algorithms is usually an exponential function with the scale which hard to uncover community structure with high speed. Inspired by the ideas of the famous modularity optimization, in this paper, we proposed a proper weighting scheme utilizing a novel k-strength relationship which naturally represents the coupling distance between two nodes. Community structure detection using a generalized weighted modularity measure is refined based on the weighted k-strength matrix. We apply our algorithm on both the famous benchmark network and the real networks. Theoretical analysis and experiments show that the weighted algorithm can uncover communities fast and accurately and can be easily extended to large-scale real networks.     

Minimum spanning trees for community detection

A simple deterministic algorithm for community detection is provided by using two rounds of minimum spanning trees. By comparing the first round minimum spanning tree (1st-MST) with the second round spanning tree (2nd-MST) of the network, communities are detected and their overlapping nodes are also identified. To generate the two MSTs, a distance matrix is defined and computed from the adjacent matrix of the network. Compared with the resistance matrix or the communicability matrix used in community detection in the literature, the proposed distance matrix is very simple in computation. The proposed algorithm is tested on real world social networks, graphs which are failed by the modularity maximization, and the LFR benchmark graphs for community detection.     

Ranking spreaders by decomposing complex networks

Ranking the nodes? ability of spreading in networks is crucial for designing efficient strategies to hinder spreading in the case of diseases or accelerate spreading in the case of information dissemination. In the well-known k-shell method, nodes are ranked only according to the links between the remaining nodes (residual links) while the links connecting to the removed nodes (exhausted links) are entirely ignored. In this Letter, we propose a mixed degree decomposition (MDD) procedure in which both the residual degree and the exhausted degree are considered. By simulating the epidemic spreading process on real networks, we show that the MDD method can outperform the k-shell and degree methods in ranking spreaders.     

Detecting and describing the modular structures of weighted networks

In the functional properties of complex networks, modules play a central role. In this paper, we propose a new method to detect and describe the modular structures of weighted networks. In order to test the proposed method, as an example, we use our method to analyse the structural properties of the Chinese railway network. Here, the stations are regarded as the nodes and the track sections are regarded as the links. Rigorous analysis of the existing data shows that using the proposed algorithm, the nodes of network can be classified naturally. Moreover, there are several core nodes in each module. Remarkably, we introduce the correlation function $G_{rs}$, and use it to distinguish the different modules in weighted networks.     

Efficient overlapping community detection in huge real-world networks

The detection of overlapping community structure in networks can give insight into the structures and functions of many complex systems. In this paper, we propose a simple but efficient overlapping community detection method for very large real-world networks. Taking a high-quality, non-overlapping partition generated by existing, efficient, non-overlapping community detection methods as input, our method identifies overlapping nodes between each pair of connected non-overlapping communities in turn. Through our analysis on modularity, we deduce that, to become an overlapping node without demolishing modularity, nodes should satisfy a specific condition presented in this paper. The proposed algorithm outputs high quality overlapping communities by efficiently identifying overlapping nodes that satisfy the above condition. Experiments on synthetic and real-world networks show that in most cases our method is better than other algorithms either in the quality of results or the computational performance. In some cases, our method is the only one that can produce overlapping communities in the very large real-world networks used in the experiments.     

Epidemic outbreaks in growing scale-free networks with local structure

The class of generative models has already attracted considerable interest from researchers in recent years and much expanded the original ideas described in BA model. Most of these models assume that only one node per time step joins the network. In this paper, we grow the network by adding n interconnected nodes as a local structure into the network at each time step with each new node emanating m new edges linking the node to the preexisting network by preferential attachment. This successfully generates key features observed in social networks. These include power-law degree distribution p_k∼k^−(3+μ), where μ=(n−1)/m is a tuning parameter defined as the modularity strength of the network, nontrivial clustering, assortative mixing, and modular structure. Moreover, all these features are dependent in a similar way on the parameter μ. We then study the susceptible-infected epidemics on this network with identical infectivity, and find that the initial epidemic behavior is governed by both of the infection scheme and the network structure, especially the modularity strength. The modularity of the network makes the spreading velocity much lower than that of the BA model. On the other hand, increasing the modularity strength will accelerate the propagation velocity.