Chinese lexical networks: The structure,function and formation

In this paper Chinese phrases are modeled using complex networks theory. We analyze statistical properties of the networks and find that phrase networks display some important features: not only small world and the power-law distribution, but also hierarchical structure and disassortative mixing. These statistical traits display the global organization of Chinese phrases. The origin and formation of such traits are analyzed from a macroscopic Chinese culture and philosophy perspective. It is interesting to find that Chinese culture and philosophy may shape the formation and structure of Chinese phrases.     

Detecting community structure in complex networks via node similarity

The detection of the community structure in networks is beneficial to understand the network structure and to analyze the network properties. Based on node similarity, a fast and efficient method for detecting community structure is proposed, which discovers the community structure by iteratively incorporating the community containing a node with the communities that contain the nodes with maximum similarity to this node to form a new community. The presented method has low computational complexity because of requiring only the local information of the network, and it does not need any prior knowledge about the communities and its detection results are robust on the selection of the initial node. Some real-world and computer-generated networks are used to evaluate the performance of the presented method. The simulation results demonstrate that this method is efficient to detect community structure in complex networks, and the ZLZ metrics used in the proposed method is the most suitable one among local indices in community detection.     

Recursive filtration method for detecting community structure in networks

Community detection is a topic of considerable recent interest within complex networks, but most methods proposed so far are divisive and agglomerative methods which delete only one edge each time to split the network, or agglomerating only one node each time until no individual node remains. Unlike those, we propose a method to split networks in parallel by deleting many edges in each filtration operation, and propose a community recursive coefficient (CRC) denoted by M instead of Q (modularity) to quantify the effect of the splitting results in this paper. We proved that recursive optimizing of the local M is equivalent to acquiring the maximal global Q value corresponding to good divisions. For a network with m edges, c communities and arbitrary topology, the method split the network at most c+1 times and detected the community structure in time O(m²+(c+1)m). We give several example applications, and show that the method can detect local communities according to the densities of external links to them in increasing order especially in large networks.     

Semi-supervised clustering algorithm for community structure detection in complex networks

Discovering a community structure is fundamental for uncovering the links between structure and function in complex networks. In this paper, we discuss an equivalence of the objective functions of the symmetric nonnegative matrix factorization (SNMF) and the maximum optimization of modularity density. Based on this equivalence, we develop a new algorithm, named the so-called SNMF-SS, by combining SNMF and a semi-supervised clustering approach. Previous NMF-based algorithms often suffer from the restriction of measuring network topology from only one perspective, but our algorithm uses a semi-supervised mechanism to get rid of the restriction. The algorithm is illustrated and compared with spectral clustering and NMF by using artificial examples and other classic real world networks. Experimental results show the significance of the proposed approach, particularly, in the cases when community structure is obscure.     

Growing community networks with local events

The study of community networks has attracted considerable attention recently. In this paper, we propose an evolving community network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Employing growth and preferential attachment mechanisms, we generate networks with a generalized power-law distribution of nodes’ degrees.     

Accuracy and precision of methods for community identification in weighted networks

Different algorithms, which take both links and link weights into account for the community structure of weighted networks, have been reported recently. Based on the measure of similarity among community structures introduced in our previous work, in this paper, accuracy and precision of three algorithms are investigated. Results show that Potts model based algorithm and weighted extremal optimization (WEO) algorithm work well on both dense or sparse weighted networks, while weighted Girvan–Newman (WGN) algorithm works well only for relatively sparse networks.     

Clustering coefficient and community structure of bipartite networks

Many real-world networks display natural bipartite structure, where the basic cycle is a square. In this paper, with the similar consideration of standard clustering coefficient in binary networks, a definition of the clustering coefficient for bipartite networks based on the fraction of squares is proposed. In order to detect community structures in bipartite networks, two different edge clustering coefficients LC₄ and LC₃ of bipartite networks are defined, which are based on squares and triples respectively. With the algorithm of cutting the edge with the least clustering coefficient, communities in artificial and real world networks are identified. The results reveal that investigating bipartite networks based on the original structure can show the detailed properties that is helpful to get deep understanding about the networks.     

A fast and efficient heuristic algorithm for detecting community structures in complex networks

Community structure is an important property of complex networks. How to detect the communities is significant for understanding the network structure and to analyze the network properties. Many algorithms, such as K-L and GN, have been proposed to detect community structures in complex networks. According to daily experience, a community should have many nodes and connections. Based on these principles and existing researches, a fast and efficient algorithm for detecting community structures in complex networks is proposed in this paper. The key strategy of the algorithm is to mine a node with the closest relations with the community and assign it to this community. Four real-world networks are used to test the performance of the algorithm. Experimental results demonstrate that the algorithm proposed is rather efficient for detecting community structures in complex networks.     

The effect of weight on community structure of networks

The effect of weight on community structures is investigated in this paper. We use weighted modularity Q^w$Q^w$ to evaluate the partitions and weighted extremal optimization algorithm to detect communities. Starting from empirical and idealized weighted networks, the matching between weights and edges are disturbed. Then using similarity function S to measure the difference between community structures, it is found that the redistribution of weights does strongly affect the community structure especially in dense networks. This indicates that the community structure in networks is a suitable property to reflect the role of weight.     

Community structure and ethnic preferences in school friendship networks

Recently developed concepts and techniques of analyzing complex systems provide new insight into the structure of social networks. Uncovering recurrent preferences and organizational principles in such networks is a key issue to characterize them. We investigate school friendship networks from the Add Health database. Applying threshold analysis, we find that the friendship networks do not form a single connected component through mutual strong nominations within a school, while under weaker conditions such interconnectedness is present. We extract the networks of overlapping communities at the schools (c-networks) and find that they are scale free and disassortative in contrast to the direct friendship networks, which have an exponential degree distribution and are assortative. Based on the network analysis we study the ethnic preferences in friendship selection. The clique percolation method we use reveals that when in minority, the students tend to build more densely interconnected groups of friends. We also find an asymmetry in the behavior of black minorities in a white majority as compared to that of white minorities in a black majority.     

Phase synchronization on small-world networks with community structure

In this paper, we propose a simple model that can generate small-world network with community structure. The network is introduced as a tunable community organization with parameter r, which is directly measured by the ratio of inter- to intra-community connectivity, and a smaller r corresponds to a stronger community structure. The structure properties, including the degree distribution, clustering, the communication efficiency and modularity are also analysed for the network. In addition, by using the Kuramoto model, we investigated the phase synchronization on this network, and found that increasing the fuzziness of community structure will markedly enhance the network synchronizability; however, in an abnormal region (r ≤ 0.001), the network has even worse synchronizability than the case of isolated communities (r = 0). Furthermore, this network exhibits a remarkable synchronization behaviour in topological scales: the oscillators of high densely interconnected communities synchronize more easily, and more rapidly than the whole network.     

Density-based shrinkage for revealing hierarchical and overlapping community structure in networks

The investigation of community structure in networks is an important issue in many disciplines, which still remains a challenging task. First, complex networks often show a hierarchical structure with communities embedded within other communities. Moreover, communities in the network may overlap and have noise, e.g., some nodes belonging to multiple communities and some nodes marginally connected with the communities, which are called hub and outlier, respectively. Therefore, a good algorithm is desirable to be able to not only detect hierarchical communities, but also to identify hubs and outliers. In this paper, we propose a parameter-free hierarchical network clustering algorithm DenShrink. By combining the advantages of density-based clustering and modularity optimization methods, our algorithm can reveal the embedded hierarchical community structure efficiently in large-scale weighted undirected networks, and identify hubs and outliers as well. Moreover, it overcomes the resolution limit possessed by other modularity-based methods. Our experiments on the real-world and synthetic datasets show that DenShrink generates more accurate results than the baseline methods.     

Detecting the community structure in complex networks based on quantum mechanics

In this paper, we develop a novel method to detect the community structure in complex networks. This approach is based on the combination of kernel-based clustering using quantum mechanics, the spectral clustering technique and the concept of the Bayesian information criterion. We test the proposed algorithm on Zachary’s karate club network and the world of American college football. Experimental results indicate that our algorithm is efficient and effective at finding both the optimal number of clusters, and the best clustering of community structures.     

Traffic dynamics in scale-free networks with tunable strength of community structure

In this paper we systematically investigate the impact of community structure on traffic dynamics in scale-free networks based on local routing strategy. A growth model is introduced to construct scale-free networks with tunable strength of community structure, and a packet routing strategy with a parameter α is used to deal with the navigation and transportation of packets simultaneously. Simulations show that the maximal network capacity stands at α=−1 in the case of identical vertex capacity and monotonously decreases with the strength of community structure which suggests that the networks with fuzzy community structure (i.e., community strength is weak) are more efficient in delivering packets than those with pronounced community structure. To explain these results, the distribution of packets of each vertex is carefully studied. Our results indicate that the moderate strength of community structure is more convenient for the information transfer of real complex systems.     

复杂网络中社团结构发现的多分辨率密度模块度

现实中的许多复杂网络呈现出明显的模块性或社团性.模块度是衡量社团结构划分优劣的效益函数, 它也通常被用作社团结构探测的目标函数,但最为广泛使用的Newman-Girvan模块度却存在着分辨率限制问题,多分辨率模块度也不能克服误合并社团和误分裂社团同时存在的缺陷. 本文在网络密度的基础上提出了多分辨率的密度模块度函数, 通过实验和分析证实了该函数能够使社团结构的误划分率显著降低, 而且能够体现出网络社团结构是一个有机整体,不是各个社团的简单相加.     

Detection of community structure in networks based on community coefficients

Determining community structure in networks is fundamental to the analysis of the structural and functional properties of those networks, including social networks, computer networks, and biological networks. Modularity function Q$Q$, which was proposed by Newman and Girvan, was once the most widely used criterion for evaluating the partition of a network into communities. However, modularity Q$Q$ is subject to a serious resolution limit. In this paper, we propose a new function for evaluating the partition of a network into communities. This is called community coefficient C$C$. Using community coefficient C$C$, we can automatically identify the ideal number of communities in the network, without any prior knowledge. We demonstrate that community coefficient C$C$ is superior to the modularity Q$Q$ and does not have a resolution limit. We also compared the two widely used community structure partitioning methods, the hierarchical partitioning algorithm and the normalized cuts (Ncut) spectral partitioning algorithm. We tested these methods on computer-generated networks and real-world networks whose community structures were already known. The Ncut algorithm and community coefficient C$C$ were found to produce better results than hierarchical algorithms. Unlike several other community detection methods, the proposed method effectively partitioned the networks into different community structures and indicated the correct number of communities.     

Detecting community structure using biased random merging

Decomposing a network into small modules or communities is beneficial for understanding the structure and dynamics of the network. One of the most prominent approaches is to repeatedly join communities together in pairs with the greatest increase in modularity so that a dendrogram that shows the order of joins is obtained. Then the community structure is acquired by cutting the dendrogram at the levels corresponding to the maximum modularity. However, there tends to be multiple pairs of communities that share the maximum modularity increment and the greedy agglomerative procedure may only merge one of them. Although the modularity function typically admits a lot of high-scoring solutions, the greedy strategy may fail to reach any of them. In this paper we propose an enhanced data structure in order to enable diverse choices of merging operations in community finding procedure. This data structure is actually a max-heap equipped with an extra array that stores the maximum modularity increments; and the corresponding community pairs is merged in the next move. By randomly sampling elements in this head array, additional diverse community structures can be efficiently extracted. The head array is designed to host the community pairs corresponding to the most significant increments in modularity so that the modularity structures obtained out of the sampling exhibit high modularity scores that are, on the average, even greater than what the CNM algorithm produces. Our method is tested on both real-world and computer-generated networks.     

网络的模块矩阵及其社团结构指标

探讨了复杂网络的模块矩阵的正(负)特征谱与网络的社团结构(反社团结构)的关系,给出了反映网络社团结构性质的相关定义.利用模块矩阵的多个特征值与特征向量,引入反映个体对所处社团的依附程度一种结构中心化指标.利用人工网络与实际网络数据,将这种指标与几种经典的中心化指标进行了比较.结果表明该指标具有较好的分辨率并与度指标具有一定程度的相关性.     

Inferring topological features of proteins from amino acid residue networks

Topological properties of native folds are obtained from statistical analysis of 160 low homology proteins covering the four structural classes. This is done analyzing one, two and three-vertex joint distribution of quantities related to the corresponding network of amino acid residues. Emphasis on the amino acid residue hydrophobicity leads to the definition of their center of mass as vertices in this contact network model with interactions represented by edges. The network analysis helps us to interpret experimental results such as hydrophobic scales and fraction of buried accessible surface area in terms of the network connectivity. Moreover, those networks show assortative mixing by degree. To explore the vertex-type dependent correlations, we build a network of hydrophobic and polar vertices. This procedure presents the wiring diagram of the topological structure of globular proteins leading to the following attachment probabilities between hydrophobic–hydrophobic 0.424(5), hydrophobic-polar 0.419(2) and polar–polar 0.157(3) residues.