Fuzzy analysis of community detection in complex networks

A snowball algorithm is proposed to find community structures in complex networks by introducing the definition of community core and some quantitative conditions. A community core is first constructed, and then its neighbors, satisfying the quantitative conditions, will be tied to this core until no node can be added. Subsequently, one by one, all communities in the network are obtained by repeating this process. The use of the local information in the proposed algorithm directly leads to the reduction of complexity. The algorithm runs in O(n+m) time for a general network and O(n) for a sparse network, where n is the number of vertices and m is the number of edges in a network. The algorithm fast produces the desired results when applied to search for communities in a benchmark and five classical real-world networks, which are widely used to test algorithms of community detection in the complex network. Furthermore, unlike existing methods, neither global modularity nor local modularity is utilized in the proposal. By converting the considered problem into a graph, the proposed algorithm can also be applied to solve other cluster problems in data mining.     

Detecting community structure in complex networks based on a measure of information discrepancy

Properties of complex networks, such as small-world property, power-law degree distribution, network transitivity, and network- community structure which seem to be common to many real-world networks have attracted great interest among researchers. In this study, global information of the networks is considered by defining the profile of any node based on the shortest paths between it and all the other nodes in the network; then a useful iterative procedure for community detection based on a measure of information discrepancy and the popular modular function Q is presented. The new iterative method does not need any prior knowledge about the community structure and can detect an appropriate number of communities, which can be hub communities or non-hub communities. The computational results of the method on real networks confirm its capability.     

Fuzzy overlapping community detection based on local random walk and multidimensional scaling

A fuzzy overlapping community is an important kind of overlapping community in which each node belongs to each community to different extents. It exists in many real networks but how to identify a fuzzy overlapping community is still a challenging task. In this work, the concept of local random walk and a new distance metric are introduced. Based on the new distance measurement, the dissimilarity index between each node of a network is calculated firstly. Then in order to keep the original node distance as much as possible, the network structure is mapped into low-dimensional space by the multidimensional scaling (MDS). Finally, the fuzzy c$c$-means clustering is employed to find fuzzy communities in a network. The experimental results show that the proposed algorithm is effective and efficient to identify the fuzzy overlapping communities in both artificial networks and real-world networks.     

Detecting communities in clustered networks based on group action on set

In this paper, we propose a well targeted algorithm (GAS algorithm) for detecting communities in high clustered networks by presenting group action technology on community division. During the processing of this algorithm, the underlying community structure of a clustered network emerges simultaneously as the corresponding partition of orbits by the permutation groups acting on the node set are achieved. As the derivation of the orbit partition, an algebraic structure r-cycle can be considered as the origin of the community. To be a priori estimation for the community structure of the algorithm, the community separability is introduced to indicate whether a network has distinct community structure. By executing the algorithm on several typical networks and the LFR benchmark, it shows that this GAS algorithm can detect communities accurately and effectively in high clustered networks. Furthermore, we compare the GAS algorithm and the clique percolation algorithm on the LFR benchmark. It is shown that the GAS algorithm is more accurate at detecting non-overlapping communities in clustered networks. It is suggested that algebraic techniques can uncover fresh light on detecting communities in complex networks.     

A thermal flux-diffusing model for complex networks and its applications in community structure detection

We introduce a thermal flux-diffusing model for complex networks. Based on this model, we propose a physical method to detect the communities in the complex networks. The method allows us to obtain the temperature distribution of nodes in time that scales linearly with the network size. Then, the local community enclosing a given node can be easily detected for the reason that the dense connections in the local communities lead to the temperatures of nodes in the same community being close to each other. The community structure of a network can be recursively detected by randomly choosing the nodes outside the detected local communities. In the experiments, we apply our method to a set of benchmarking networks with known pre-determined community structures. The experiment results show that our method has higher accuracy and precision than most existing globe methods and is better than the other existing local methods in the selection of the initial node. Finally, several real-world networks are investigated.     

A local fuzzy method based on “p-strong” community for detecting communities in networks

In this paper,we propose a local fuzzy method based on the idea of "p-strong" community to detect the disjoint and overlapping communities in networks.In the method,a refined agglomeration rule is designed for agglomerating nodes into local communities,and the overlapping nodes are detected based on the idea of making each community strong.We propose a contribution coefficient b_v~(ci)to measure the contribution of an overlapping node to each of its belonging communities,and the fuzzy coefficients of the overlapping node can be obtained by normalizing the b_v~(ci) to all its belonging communities.The running time of our method is analyzed and varies linearly with network size.We investigate our method on the computergenerated networks and real networks.The testing results indicate that the accuracy of our method in detecting disjoint communities is higher than those of the existing local methods and our method is efficient for detecting the overlapping nodes with fuzzy coefficients.Furthermore,the local optimizing scheme used in our method allows us to partly solve the resolution problem of the global modularity.     

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.     

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.     

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.     

Exact solution of the 1D Hubbard model with NN and NNN interactions in the narrow-band limit

In this paper, we propose a family of weighted extended Koch networks based on a class of extended Koch networks. They originate from a r-complete graph, and each node in each r-complete graph of current generation produces mr-complete graphs whose weighted edges are scaled by factor h in subsequent evolutionary step. We study the structural properties of these networks and random walks on them. In more detail, we calculate exactly the average weighted shortest path length (AWSP), average receiving time (ART) and average sending time (AST). Besides, the technique of resistor network is employed to uncover the relationship between ART and AST on networks with unit weight. In the infinite network order limit, the average weighted shortest path lengths stay bounded with growing network order (0 < h < 1). The closed form expression of ART shows that it exhibits a sub-linear dependence (0 < h < 1) or linear dependence (h = 1) on network order. On the contrary, the AST behaves super-linearly with the network order. Collectively, all the obtained results show that the efficiency of message transportation on weighted extended Koch networks has close relation to the network parameters h, m and r. All these findings could shed light on the structure and random walks of general weighted networks.     

加权网络权重自相似评判函数及其社团结构检测

提出了权重自相似性加权网络社团结构评判函数,并基于该函数提出一种谱分析算法检测社团结构,结果表明算法能将加权网络划分为同一社团内边权值分布均匀,而社团间边权值分布随机的社团结构.通过建立具有社团结构的加权随机网络分析了该算法的准确性,与WEO和WGN算法相比,在评判权重自相似的阈值系数取较小时,该算法具有较高的准确性.对于一个具有n个节点和c个社团的加权网络,社团结构检测的复杂度为O(cn2/2).通过设置评判权重自相似的阈值系数,可检测出能反映节点联系稳定性的层化性社团结构.这与传统意义上只将加权网络划分为社团中边权值较大而社团间边权值较小的标准不同,从另一个角度更好地提取了加权网络的结构信息.     

Modularity functions maximization with nonnegative relaxation facilitates community detection in networks

We show here that the problem of maximizing a family of quantitative functions, encompassing both the modularity (Q-measure) and modularity density (D-measure), for community detection can be uniformly understood as a combinatoric optimization involving the trace of a matrix called modularity Laplacian. Instead of using traditional spectral relaxation, we apply additional nonnegative constraint into this graph clustering problem and design efficient algorithms to optimize the new objective. With the explicit nonnegative constraint, our solutions are very close to the ideal community indicator matrix and can directly assign nodes into communities. The near-orthogonal columns of the solution can be reformulated as the posterior probability of corresponding node belonging to each community. Therefore, the proposed method can be exploited to identify the fuzzy or overlapping communities and thus facilitates the understanding of the intrinsic structure of networks. Experimental results show that our new algorithm consistently, sometimes significantly, outperforms the traditional spectral relaxation approaches.     

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.     

Ubiquitousness of link-density and link-pattern communities in real-world networks

Many networks are characterized by the presence of communities, densely intra-connected groups with sparser inter-connections between groups. We propose a community overlay network representation to capture large-scale properties of communities. A community overlay G _o can be constructed upon a network G, called the underlying network, by (a) aggregating each community in G as a node in the overlay G _o ; (b) connecting two nodes in the overlay if the corresponding two communities in the underlying network have a number of direct links in between, (c) assigning to each node/link in the overlay a node/link weight, which represents e.g. the percentage of links in/between the corresponding underlying communities. The community overlays have been constructed upon a large number of real-world networks based on communities detected via five algorithms. Surprisingly, we find the following seemingly universal properties: (i) an overlay has a smaller degree-degree correlation than its underlying network ρ _o (D _l+, D _l−) < ρ(D _l+, D _l−) and is mostly disassortative ρ _o (D _l+, D _l−) < 0; (ii) a community containing a large number W _i of nodes tends to connect to many other communities ρ _o (W _i , D _i ) > 0. We explain the generic observation (i) by two facts: (1) degree-degree correlation or assortativity tends to be positively correlated with modularity; (2) by aggregating each community as a node, the modularity in the overlay is reduced and so is the assortativity. The observation (i) implies that the assortativity of a network depends on the aggregation level of the network representation, which is illustrated by the Internet topology at router and AS level.     

Average weighted receiving time in recursive weighted Koch networks

Motivated by the empirical observation in airport networks and metabolic networks, we introduce the model of the recursive weighted Koch networks created by the recursive division method. As a fundamental dynamical process, random walks have received considerable interest in the scientific community. Then, we study the recursive weighted Koch networks on random walk i.e., the walker, at each step, starting from its current node, moves uniformly to any of its neighbours. In order to study the model more conveniently, we use recursive division method again to calculate the sum of the mean weighted first-passing times for all nodes to absorption at the trap located in the merging node. It is showed that in a large network, the average weighted receiving time grows sublinearly with the network order.     

Overlapping community detection using a generative model for networks

Detecting overlapping communities is a challenging task in analyzing networks, where nodes may belong to more than one community. Many present methods optimize quality functions to extract the communities from a network. In this paper, we present a probabilistic method for detecting overlapping communities using a generative model. The model describes the probability of generating a network with the model parameters, which reflect the communities in the network. The community memberships of each node are determined based on a probabilistic approach using those model parameters, whose values can be obtained by fitting the model to the network. This method has the advantage that the node participation degrees in each community are also computed. The proposed method is compared with some other community detection methods on both synthetic networks and real-world networks. The experiments show that this method is efficient at detecting overlapping communities and can provide better performance on the networks where a majority of nodes belong to more than one community.     

Detecting the optimal number of communities in complex networks

To obtain the optimal number of communities is an important problem in detecting community structures. In this paper, we use the extended measurement of community detecting algorithms to find the optimal community number. Based on the normalized mutual information index, which has been used as a measure for similarity of communities, a statistic Ω(c) is proposed to detect the optimal number of communities. In general, when Ω(c) reaches its local maximum, especially the first one, the corresponding number of communities c is likely to be optimal in community detection. Moreover, the statistic Ω(c) can also measure the significance of community structures in complex networks, which has been paid more attention recently. Numerical and empirical results show that the index Ω(c) is effective in both artificial and real world networks.     

First observation of the production and decay of the Σc+

An event with the decay chain Σ_c⁺ → Λ_c⁺ + π⁰, Λ_c⁺ → K^? + p + π⁺, has been observed in an exposure of BEBC, equipped with a track sensitive target, to the wide band neutrino beam from the SPS at CERN. The event has a unique three constraint kinematic fit to the ΔS = ?ΔQ reaction v + p → μ^? + p + K^? + π⁺ + π⁺ + π⁰ with both gammas from the π⁰ decay detected. The proton and other final state particles are identified. The masses are M(Λ_c⁺) = 2290 ± 3 MeV/c², M(Σ_c⁺) = 2457 ± 4 MeV/c² and M(Σ_c⁺) ? M(Λ_c⁺) = 168 ± 3 MeV/c². Including other data one obtains M (Σ_c⁺⁺) ? M(Σ_c⁺) = 0 ± 4 MeV/c².     

Optimal routing strategy based on the minimum information path

In this paper, we propose a new routing strategy based on the minimum information path, named the optimal routing (OR) strategy, to improve the transportation capacity of scale-free networks. We define the average routing centrality degree of the node to analyze the traffic load on nodes of different degree. We analyze the transportation capacity by using the critical values of R_c, the average packet travel time, and the average path length. Both theoretical and experimental results show that the capacity of the network under our strategy will be maximized when the packet-delivery rate of the node is directly proportional to the degree.     

Community structure of complex software systems: Analysis and applications

Due to notable discoveries in the fast evolving field of complex networks, recent research in software engineering has also focused on representing software systems with networks. Previous work has observed that these networks follow scale-free degree distributions and reveal small-world phenomena, while we here explore another property commonly found in different complex networks, i.e. community structure. We adopt class dependency networks, where nodes represent software classes and edges represent dependencies among them, and show that these networks reveal a significant community structure, characterized by similar properties as observed in other complex networks. However, although intuitive and anticipated by different phenomena, identified communities do not exactly correspond to software packages. We empirically confirm our observations on several networks constructed from Java and various third party libraries, and propose different applications of community detection to software engineering.