Adjusting from disjoint to overlapping community detection of complex networks

The investigation of community structures is one of the most important problems in the field of complex networks and has countless applications in different disciplines: biology, computer, social sciences, etc. Many community detection algorithms have been developed in various fields recently. The vast majority of these algorithms only find disjoint communities; however, in many real-world networks communities often overlap to some extent. In this paper, we propose an efficient method for adjusting these classical algorithms to match the requirement for discovering overlapping communities in complex networks, which is based on a local definition of community strength. The method can in principle be applied with any clustering algorithm. Tests on a set of computer generated and real-world networks give excellent results. In particular, we show that the method can also allow one to availably analyze the problem of unstable nodes in community detection, which is very helpful for understanding the structural properties of the networks correctly and comprehensively.     

Cumulative Laws, Team Assembling Mechanisms Determining Network Structure

A number of researching works have shed light on the field of complex networks recently. We investigate a wide range of real-world networks and find several interesting phenomena. Firstly, almost all of these networks evolve by overlapping new small graphs on former networks. Secondly, not only the degree sequence of the mature network follows a power-law distribution, but also the distribution of the cumulative occurrence times during the growing process are revealed to have a heavy tail. Existing network evolving models do not provide interpretation to these phenomena. We suggest a model based on the team assembling mechanism, which is extracted from the growing processes of real-world networks and requires simple parameters, and produces networks exhibiting these properties observed in the present study and in previous works.     

Network robustness to targeted attacks. The interplay of expansibility and degree distribution

We study the property of certain complex networks of being both sparse and highly connected, which is known as “good expansion” (GE). A network has GE properties if every subset S of nodes (up to 50% of the nodes) has a neighborhood that is larger than some “expansion factor” φ multiplied by the number of nodes in S. Using a graph spectral method we introduce here a new parameter measuring the good expansion character of a network. By means of this parameter we are able to classify 51 real-world complex networks — technological, biological, informational, biological and social — as GENs or non-GENs. Combining GE properties and node degree distribution (DD) we classify these complex networks in four different groups, which have different resilience to intentional attacks against their nodes. The simultaneous existence of GE properties and uniform degree distribution contribute significantly to the robustness in complex networks. These features appear solely in 14% of the 51 real-world networks studied here. At the other extreme we find that ∼40% of all networks are very vulnerable to targeted attacks. They lack GE properties, display skewed DD — exponential or power-law — and their topologies are changed more dramatically by targeted attacks directed at bottlenecks than by the removal of network hubs.     

Statistical properties of weighted complex networks characterized by metaweights

We propose several characterizations of weighted complex networks by incorporating the concept of metaweight into the clustering coefficient, degree correlation, and module decomposition. These incorporations make it possible to describe weighted networks depending on how strongly we emphasize weights. Using some applications to real-world weighted networks, we demonstrate that the proposed approach provides rich information that was inaccessible by previous analyses such as the degree correlation for a specific magnitude of weights or the community structure under controlling the importance of roles of the topology and weights.     

Stability of the BA Network: a New Approach to Rigorous Proof

We propose a new approach to rigorously prove the existence of the steady-state degree distribution for the BA network. The approach is based on a vector Markov chain of vertex numbers in the network evolving process. This framework provides a rigorous theoretical basis for the rate equation approach which has been widely applied to many problems in the field of complex networks, e.g., epidemic spreading and dynamic synchronization.     

A very fast algorithm for detecting community structures in complex networks

In this paper, a new algorithm is proposed, which uses only local information to analyze community structures in complex networks. The algorithm is based on a table that describes a network and a virtual cache similar to the cache in the computer structure. When being tested on some typical computer-generated and real-world networks, this algorithm demonstrates excellent detection results and very fast processing performance, much faster than the existing comparable algorithms of the same kind.     

A class of improved algorithms for detecting communities in complex networks

Detecting communities in complex networks is of considerable importance for understanding both the structure and function of the networks. Here, we propose a class of improved algorithms for community detection, by combining the betweenness algorithm of Girvan and Newman with the edge weight defined by the edge-clustering coefficient. The improved algorithms are tested on some artificial and real-world networks, and the results show that they can detect communities of networks more effectively in both unweighted and weighted cases. In addition, the technique for improving the betweenness algorithm in this paper, thanks to its compatibility, can directly be applied to various detection algorithms.     

Synchronization in complex networks

Synchronization processes in populations of locally interacting elements are the focus of intense research in physical, biological, chemical, technological and social systems. The many efforts devoted to understanding synchronization phenomena in natural systems now take advantage of the recent theory of complex networks. In this review, we report the advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology. We also take an overview of the new emergent features coming out from the interplay between the structure and the function of the underlying patterns of connections. Extensive numerical work as well as analytical approaches to the problem are presented. Finally, we review several applications of synchronization in complex networks to different disciplines: biological systems and neuroscience, engineering and computer science, and economy and social sciences.     

Cascading Failures of Complex Networks Based on Two-Step Degree

We propose a new concept, two-step degree. Defining it as the capacity of a node of complex networks, we establish a novel capacity-load model of cascading failures of complex networks where the capacity of nodes decreases during the process of cascading failures. For scale-free networks, we find that the average two-step degree increases with the increase of the heterogeneity of the degree distribution, showing that the average two- step degree can be used for measuring the heterogeneity of the degree distribution of complex networks. In addition, under the condition that the average degree of a node is given, we can design a scale-free network with the optimal robustness to random failures by maximizing the average two-step degree.     

A Law of Gravitation for Complex Networks

Inspiring Newton＇s law of universal gravitation and empirical studies, we propose a concept of virtual network mass and network gravitational force in complex networks. Then a network gravitational model for complex networks is presented. In the model, each node in the network is described with its position, edges （links） and virtual network mass. The proposed model is examined by experiments to show its potential applications.     

An empirical study of Chinese language networks

Chinese is spoken by the largest number of people in the world, and it is regarded as one of the most important languages. In this paper, we explore the statistical properties of Chinese language networks (CLNs) within the framework of complex network theory. Based on one of the largest Chinese corpora, i.e. People’s Daily Corpus, we construct two networks (CLN1 and CLN2) from two different respects, with Chinese words as nodes. In CLN1, a link between two nodes exists if they appear next to each other in at least one sentence; in CLN2, a link represents that two nodes appear simultaneously in a sentence. We show that both networks exhibit small-world effect, scale-free structure, hierarchical organization and disassortative mixing. These results indicate that in many topological aspects Chinese language shapes complex networks with organizing principles similar to other previously studied language systems, which shows that different languages may have some common characteristics in their evolution processes. We believe that our research may shed some new light into the Chinese language and find some potentially significant implications.     

Assortativeness and information in scale-free networks

We analyze Shannon information of scale-free networks in terms of their assortativeness, and identify classes of networks according to the dependency of the joint remaining degree distribution on the assortativeness. We conjecture that these classes comprise minimalistic and maximalistic networks in terms of Shannon information. For the studied classes, the information is shown to depend non-linearly on the absolute value of the assortativeness, with the dominant term of the relationship being a power-law. We exemplify this dependency using a range of real-world networks. Optimization of scale-free networks according to information they contain depends on the landscape of parameters’ search-space, and we identify two regions of interest: a slope region and a stability region. In the slope region, there is more freedom to generate and evaluate candidate networks since the information content can be changed easily by modifying only the assortativeness, while even a small change in the power-law’s scaling exponent brings a reward in a higher rate of information change. This feature may explain why the exponents of real-world scale-free networks are within a certain range, defined by the slope and stability regions.     

Network Entropy Based on Topology Configuration and Its Computation to Random Networks

A definition of network entropy is presented, and as an example, the relationship between the value of network entropy of ER network model and the connect probability p as well as the total nodes N is discussed. The theoretical result and the simulation result based on the network entropy of the ER network are in agreement well with each other. The result indicated that different from the other network entropy reported before, the network entropy defined here has an obvious difference from different type of random networks or networks having different total nodes. Thus, this network entropy may portray the characters of complex networks better. It is also pointed out that, with the aid of network entropy defined, the concept of equilibrium networks and the concept of non-equilibrium networks may be introduced, and a quantitative measurement to describe the deviation to equilibrium state of a complex network is carried out.     

On the rich-club effect in dense and weighted networks

For many complex networks present in nature only a single instance, usually of large size, is available. Any measurement made on this single instance cannot be repeated on different realizations. In order to detect significant patterns in a real-world network it is therefore crucial to compare the measured results with a null model counterpart. Here we focus on dense and weighted networks, proposing a suitable null model and studying the behaviour of the degree correlations as measured by the rich-club coefficient. Our method solves an existing problem with the randomization of dense unweighted graphs, and at the same time represents a generalization of the rich-club coefficient to weighted networks which is complementary to other recently proposed ones.     

Accessibility in complex networks

This Letter describes a method for the quantification of the diversity of non-linear dynamics in complex networks as a consequence of self-avoiding random walks. The methodology is analyzed in the context of theoretical models and illustrated with respect to the characterization of the accessibility in urban streets.     

Robustness of Complex Networks under Attack and Repair

To study the robustness of complex networks under attack and repair, we introduce a repair model of complex networks. Based on the model, we introduce two new quantities, i.e. attack fraction fa and the maximum degree of the nodes that have never been attacked ~Ka, to study analytically the critical attack fraction and the relative size of the giant component of complex networks under attack and repair, using the method of generating function. We show analytically and numerically that the repair strategy significantly enhances the robustness of the scale-free network and the effect of robustness improvement is better for the scale-free networks with a smaller degree exponent. We discuss the application of our theory in relation to the
understanding of robustness of complex networks with reparability.     

Effect of Eliminating Edges on Robustness of Scale-Free Networks under Intentional Attack

We study the robustness of complex networks under edge elimination. We propose three different edge elimination strategies and investigate their effects on the robustness of scale-free networks under intentional attack. We show that deleting a proper fraction of edges connecting hub nodes and hub nodes can enhance the robustness of scale-free networks under intentional attack.     

The emergence of scale-free networks with a seceding mechanism

In order to explore further the underlying mechanism of scale-free networks, we study stochastic secession as a mechanism for the creation of complex networks. In this evolution the network growth incorporates the addition of new nodes, the addition of new links between existing nodes, the deleting and rewiring of some existing links, and the stochastic secession of nodes. To random growing networks with preferential attachment, the model yields scale-free behavior for the degree distribution. Furthermore, we obtain an analytical expression of the power-law degree distribution with scaling exponent γ ranging from 1.1 to 9. The analytical expressions are in good agreement with the numerical simulation results.     

Improvement of Synchronizability of Scale-Free Networks

We investigate the factors that affect synchronizability of coupled oscillators on scale-free networks. Using the memory Tabu search （MTS） algorithm, we improve the eigen-ratio Q of a coupling matrix by edge intercrossing. The numerical results show that the synchronizatlon-improved scale-free networks should have distinctive both small average distance and larger clustering coefficient, which are consistent with some real-world networks. Moreover, the synchronizability-improved networks demonstrate the disassortative coefficient.