Narrow Results

The investigation of community structures in complex networks is an important issue in many domains and disciplines. In this paper, we propose a novel method to address the problem based on evaluation of the community structure. By testing the proposed algorithm on artificial and real-world networks, experimental results demonstrate that our approach is both accurate and fast. Our algorithm may shed light on uncovering the universal principles of network architectures and topologies.

Speech sounds of the languages all over the world show remarkable patterns of co-occurrence. In this work, we attempt to automatically capture the patterns of co-occurrence of the consonants across languages and at the same time figure out the nature of the force leading to the emergence of such patterns. For this purpose we define a weighted network where the consonants are the nodes and an edge between two nodes (read consonants) signify their co-occurrence likelihood over the consonant inventories. Through this network we identify communities of consonants that essentially reflect their patterns of co-occurrence across languages. We test the goodness of the communities and observe that the constituent consonants frequently occur in such groups in real languages also. Interestingly, the consonants forming these communities reflect strong correlations in terms of their features, which indicate that the principle of feature economy acts as a driving force towards community formation. In order to measure the strength of this force we propose a theoretical information definition of feature economy and show that indeed the feature economy exhibited by the consonant communities are substantially better than that of those where the consonant inventories had evolved just by chance.

Community structure is an important topological phenomenon typical of complex networks. Accurately unveiling communities is thus crucial to understand and capture the many-faceted nature of complex networks. Communities in real world frequently overlap, i.e. nodes can belong to more than one community. Therefore, quantitatively evaluating the extent to which a node belongs to a community is a key step to find overlapping boundaries between communities. Non-negative matrix factorization (NMF) is a technique that has been used to detect overlapping communities. However, previous efforts in this direction present: (i) limitations in the interpretation of meaningful overlaps and (ii) lack of accuracy in predicting the correct number of communities. In this paper, a hybrid method of NMF to overcome both limitations is presented. This approach effectively estimates the number of communities and is more interpretable and more accurate in identifying overlapping communities in undirected networks than previous approaches. Validations on synthetic and real world networks show that the proposed community learning framework can effectively reveal overlapping communities in complex networks.

This study explores the community structure in spatial maritime shipping networks. As compared with air transportation networks and urban road networks, ports in spatial maritime shipping networks have smaller connections due to the physical confinement. A new divisive algorithm is proposed for detecting community structure in spatial maritime shipping networks. At each iteration for modularity optimization, the length of each edge is successively updated, instead of edge removal used in the conventional divisive method. Finally, numerical experiments based on the global maritime shipping network are carried out to account for the properties of community structure in spatial maritime shipping networks.

In this paper, based on the phenomenon that individuals join into and jump from the organizations in the society, we propose a dynamic community model to construct social networks. Two parameters are adopted in our model, one is the communication rate P_a that denotes the connection strength in the organization and the other is the turnover rate P_b, that stands for the frequency of jumping among the organizations. Based on simulations, we analyze not only the degree distribution, the clustering coefficient, the average distance and the network diameter but also the group distribution which is closely related to their community structure. Moreover, we discover that the networks generated by the proposed model possess the small-world property and can well reproduce the networks of social contacts.

Much empirical evidence shows that when attacked with cascading failures, scale-free or even random networks tend to collapse more extensively when the initially deleted node has higher betweenness. Meanwhile, in networks with strong community structure, high-betweenness nodes tend to be bridge nodes that link different communities, and the removal of such nodes will reduce only the connections among communities, leaving the networks fairly stable. Understanding what will affect cascading failures and how to protect or attack networks with strong community structure is therefore of interest. In this paper, we have constructed scale-free Community Networks (SFCN) and Random Community Networks (RCN). We applied these networks, along with the Lancichinett–Fortunato–Radicchi (LFR) benchmark, to the cascading-failure scenario to explore their vulnerability to attack and the relationship between cascading failures and the degree distribution and community structure of a network. The numerical results show that when the networks are of a power-law distribution, a stronger community structure will result in the failure of fewer nodes. In addition, the initial removal of the node with the highest betweenness will not lead to the worst cascading, i.e. the largest avalanche size. The Betweenness Overflow (BOF), an index that we developed, is an effective indicator of this tendency. The RCN, however, display a different result. In addition, the avalanche size of each node can be adopted as an index to evaluate the importance of the node.

This paper proposes an improved community model for social networks based on social mobility. The relationship between the group distribution and the community size is investigated in terms of communication rate and turnover rate. The degree distributions, clustering coefficients, average distances and diameters of networks are analyzed. Experimental results demonstrate that the proposed model possesses the small-world property and can reproduce social networks effectively and efficiently.

The analysis of the dynamic details of community structure is an important question for scientists from many fields. In this paper, we propose a novel Markov–Potts framework to uncover the optimal community structures and their stabilities across multiple timescales. Specifically, we model the Potts dynamics to detect community structure by a Markov process, which has a clear mathematical explanation. Then the local uniform behavior of spin values revealed by our model is shown that can naturally reveal the stability of hierarchical community structure across multiple timescales. To prove the validity, phase transition of stochastic dynamic system is used to indicate that the stability of community structure we proposed is able to describe the significance of community structure based on eigengap theory. Finally, we test our framework on some example networks and find it does not have resolute limitation problem at all. Results have shown the model we proposed is able to uncover hierarchical structure in different scales effectively and efficiently.

Network dynamics plays an important role in analyzing the correlation between the function properties and the topological structure. In this paper, we propose a novel dynamical iteration (DI) algorithm, which incorporates the iterative process of membership vector with weighting scheme, i.e. weighting W and tightness T. These new elements can be used to adjust the link strength and the node compactness for improving the speed and accuracy of community structure detection. To estimate the optimal stop time of iteration, we utilize a new stability measure which is defined as the Markov random walk auto-covariance. We do not need to specify the number of communities in advance. It naturally supports the overlapping communities by associating each node with a membership vector describing the node's involvement in each community. Theoretical analysis and experiments show that the algorithm can uncover communities effectively and efficiently.

Community structure detection is of great significance for better understanding the network topology property. By taking into account the neighbor degree information of the topological network as the link weight, we present an improved Nonnegative Matrix Factorization (NMF) method for detecting community structure. The results for empirical networks show that the largest improved ratio of the Normalized Mutual Information value could reach $63.21\%$. Meanwhile, for synthetic networks, the highest Normalized Mutual Information value could closely reach 1, which suggests that the improved method with the optimal $\lambda$ can detect the community structure more accurately. This work is helpful for understanding the interplay between the link weight and the community structure detection.

The community structure is important for software in terms of understanding the design patterns, controlling the development and the maintenance process. In order to detect the optimal community structure in the software network, a method Optimal Partition Software Network (OPSN) is proposed based on the dependency relationship among the software functions. First, by analyzing the information of multiple execution traces of one software, we construct Software Execution Dependency Network (SEDN). Second, based on the relationship among the function nodes in the network, we define Fault Accumulation (FA) to measure the importance of the function node and sort the nodes with measure results. Third, we select the top K(K=1,2,…) nodes as the core of the primal communities (only exist one core node). By comparing the dependency relationships between each node and the K communities, we put the node into the existing community which has the most close relationship. Finally, we calculate the modularity with different initial K to obtain the optimal division. With experiments, the method OPSN is verified to be efficient to detect the optimal community in various softwares.

Studies demonstrate that community structure plays an important role in information spreading recently. In this paper, we investigate the impact of multi-community structure on information diffusion with linear threshold model. We utilize extended GN network that contains four communities and analyze dynamic behaviors of information that spreads on it. And we discover the optimal multi-community network modularity for information diffusion based on the social reinforcement. Results show that, within the appropriate range, multi-community structure will facilitate information diffusion instead of hindering it, which accords with the results derived from two-community network.

In this paper, taking the traffic of Beijing city as an instance, we study city traffic states, especially traffic congestion, based on the concept of network community structure. Concretely, using the floating car data (FCD) information of vehicles gained from the intelligent transport system (ITS) of the city, we construct a new traffic network model which is with floating cars as network nodes and time-varying. It shows that this traffic network has Gaussian degree distributions at different time points. Furthermore, compared with free traffic situations, our simulations show that the traffic network generally has more obvious community structures with larger values of network fitness for congested traffic situations, and through the GPSspg web page, we show that all of our results are consistent with the reality. Then, it indicates that network community structure should be an available way for investigating city traffic congestion problems.

Community detection is one important problem in network theory, and many methods have been proposed for detecting community structures in the networks. Given quality functions for evaluating community structures, community detection can be considered as one kind of optimization problem, such as modularity optimization, therefore, optimization of quality functions has been one of the most popular strategies for community detection. In this paper, we introduced two kinds of local modularity functions for community detection, and the self-consistent method is introduced to optimize the local modularity for detecting communities in the networks. We analyze the behaviors of the modularity optimizations, and compare the performance of them in community detection. The results confirm the superiority of the local modularity in detecting community structures, especially on large-size and heterogeneous networks.

The significance of communities is an important inherent property of the community structure. It measures the degree of reliability of the community structure identified by the algorithm. Real networks obtained from complex systems always contain error links. Moreover, most of the community detecting algorithms usually involve random factors. Thus evaluating the significance of community structure is very important. In this paper, using the matrix perturbation theory, we propose a normalized index to efficiently evaluate the significance of community structure without detecting communities. Furthermore, we find that the peaks of this index can be used to determine the optimal number of communities and identify hierarchical community structure, which are two challenging problems in many community detecting algorithms. Lastly, the index is applied to 16 typical real networks, and we find that significant community structures exist in many social networks and in the C. elegans neural network. Comparatively insignificant community structures are identified in protein-interaction networks and metabolic networks. Our method can be generalized to broad clustering problems in data mining.

Community structure is a common characteristic of complex networks and community detection is an important methodology to reveal the structure of real-world networks. In recent years, many algorithms have been proposed to detect the high-quality communities in real-world networks. However, these algorithms have shortcomings of performing calculation on the whole network or defining objective function and the number of commonties in advance, which affects the performance and complexity of community detection algorithms. In this paper, a novel algorithm has been proposed to detect communities in networks by belonging intensity analysis of intermediate nodes, named BIAS, which is inspired from the interactive behavior in human communication networks. More specifically, intermediate nodes are middlemen between different groups in social networks. BIAS algorithm defines belonging intensity using local interactions and metrics between nodes, and the belonging intensity of intermediate node in different communities is analyzed to distinguish which community the intermediate node belongs to. The experiments of our algorithm with other state-of-the-art algorithms on synthetic networks and real-world networks have shown that BIAS algorithm has better accuracy and can significantly improve the quality of community detection without prior information.

The real-world network is heterogeneous, and it is an important and challenging task to effectively identify the influential nodes in complex networks. Identification of influential nodes is widely used in social, biological, transportation, information and other networks with complex structures to help us solve a variety of complex problems. In recent years, the identification of influence nodes has received a lot of attention, and scholars have proposed various methods based on different practical problems. This paper proposes a new method to identify influential nodes, namely Attraction based on Node and Community (ANC). By considering the attraction of nodes to nodes and nodes to community structure, this method quantifies the attraction of a node, and the attraction of a node is used to represent its influence. To illustrate the effectiveness of ANC, we did extensive experiments on six real-world networks and the results show that the ANC algorithm is superior to the representative algorithms in terms of the accuracy and has lower time complexity as well.

Community structure detection is one of the fundamental problems in complex network analysis towards understanding the topology structure and function of the network. Modularity is a criterion to evaluate the quality of community structures, and optimization of this quality function over the possible divisions of a network is a sensitive detection method for community structure. However, the direct application of this method is computationally costly. Nonnegative matrix factorization (NMF) is a widely used method for community detection. In this paper, we show that modularity maximization can be approximately reformulated under the framework of NMF with Frobenius norm, especially when $n$ is large. A new algorithm for detecting community structure is proposed based on the above finding. The new method is compared with four state-of-the-art methods on both synthetic and real-world networks, showing its higher clustering quality over the existing methods.

In complex networks, how topology structures influence the traffic dynamics on networks is a hot topic. The existence of structure within communities may affect the transmission of data packets in the network. In this paper, we investigate the impact of community structure on traffic dynamics in random networks which are homogeneous. It is found that three key factors influence traffic capacity in such community networks: community number, community strength, and average node degree. The increase of average node degree increases traffic capacity, while the increase of community number and community strength decreases traffic capacity.

The collective behaviors of community members in dynamic bitcoin transaction network are significant to understand the evolutionary characteristics of communities for bitcoin transaction network. In this paper, we empirically investigate the behavior evolution of new nodes forming communities for the bitcoin transaction network. First, we divide the bitcoin transaction network into multiple time segments, and detect community on each time segment. Then, according to the set similarity method, we mark the community with maximal similarity $\sigma <0.001$ at adjacent timestamps as the new community. Finally, we propose an evolution index to illustrate the evolution trend of new nodes forming communities, and introduce the reshuffle model to compare with it. The results show that there are obvious differences in the early stage, and new traders tend to join new communities. However, after August 2011, the trends of before and after reorganization are very similar, which indicates that in bitcoin trading, the behaviors of new traders forming communities become random. Our work may be helpful for the understanding of user behavior characteristics in bitcoin trading, and provide a new perspective for the research of bitcoin transaction network.