一类高聚类系数的加权无标度网络及其同步能力分析

针对真实世界中大规模网络都具有明显聚类效应的特点, 提出一类具有高聚类系数的加权无标度网络演化模型, 该模型同时考虑了优先连接、三角结构、随机连接和社团结构等四种演化机制. 在模型演化规则中, 以概率p增加单个节点, 以概率1–p增加一个社团. 与以往研究的不同在于新边的建立, 以概率φ在旧节点之间进行三角连接, 以概率1–φ进行随机连接. 仿真分析表明, 所提出的网络度、强度和权值分布都是服从幂律分布的形式, 且具有高聚类系数的特性, 聚类系数的提高与社团结构和随机连接机制有直接的关系. 最后通过数值仿真分析了网络演化机制对同步动态特性的影响, 数值仿真结果表明, 网络的平均聚类系数越小, 网络的同步能力越强. 关键词： 无标度网络 加权网络 聚类系数 同步能力     

Ant colony clustering with fitness perception and pheromone diffusion for community detection in complex networks

Community structure detection in complex networks has been intensively investigated in recent years. In this paper, we propose an adaptive approach based on ant colony clustering to discover communities in a complex network. The focus of the method is the clustering process of an ant colony in a virtual grid, where each ant represents a node in the complex network. During the ant colony search, the method uses a new fitness function to percept local environment and employs a pheromone diffusion model as a global information feedback mechanism to realize information exchange among ants. A significant advantage of our method is that the locations in the grid environment and the connections of the complex network structure are simultaneously taken into account in ants moving. Experimental results on computer-generated and real-world networks show the capability of our method to successfully detect community structures.     

Weighted Evolving Networks with Self-organized Communities

In order to describe the self-organization of communities in the evolution of weighted networks, we propose a new evolving model for weighted community-structured networks with the preferential mechanisms functioned in different levels according to community sizes and node strengths, respectively. Theoretical analyses and numerical simulations show that our model captures power-law distributions of community sizes, node strengths, and link weights, with tunable exponents of ν≥1, γ>2, and α>2, respectively, sharing large clustering coefficients and scaling clustering spectra, and covering the range from disassortative networks to assortative networks. Finally, we apply our new model to the scientific co-authorship networks with both their weighted and unweighted datasets to verify its effectiveness.     

基于联合矩阵分解的节点多属性网络社团检测

发现复杂网络中的社团结构在社会网络、生物组织网络和在线网络等复杂网络中具备十分重要的意义. 针对社交媒体网络的社团检测通常需要利用两种信息源: 网络拓扑结构特征和节点属性特征, 丰富的节点内容属性信息为社团检测的增加了灵活性和挑战. 传统方法是要么仅针对这两者信息之一进行单独挖掘, 或者将两者信息得到的社团结果进行线性叠加判决, 不能有效进行信息源的融合. 本文将节点的多维属性特征作为社团划分的一种有效协同学习项进行研究, 将两者信息源进行融合分析, 提出了一种基于联合矩阵分解的节点多属性网络社团检测算法CDJMF, 提高了社团检测的有效性和鲁棒性. 实验表明, 本文所提的方法能够有效利用节点的属性信息指导社团检测, 具备更高的社团划分质量.     

System of mobile agents to model social networks

We propose a model of mobile agents to construct social networks, based on a system of moving particles by keeping track of the collisions during their permanence in the system. We reproduce not only the degree distribution, clustering coefficient, and shortest path length of a large database of empirical friendship networks recently collected, but also some features related with their community structure. The model is completely characterized by the collision rate, and above a critical collision rate we find the emergence of a giant cluster in the universality class of two-dimensional percolation. Moreover, we propose possible schemes to reproduce other networks of particular social contacts, namely, sexual contacts.     

Community detection based on network communicability

We propose a new method for detecting communities based on the concept of communicability between nodes in a complex network. This method, designated as N-ComBa K-means, uses a normalized version of the adjacency matrix to build the communicability matrix and then applies K-means clustering to find the communities in a graph. We analyze how this method performs for some pathological cases found in the analysis of the detection limit of communities and propose some possible solutions on the basis of the analysis of the ratio of local to global densities in graphs. We use four different quality criteria for detecting the best clustering and compare the new approach with the Girvan-Newman algorithm for the analysis of two "classical" networks: karate club and bottlenose dolphins. Finally, we analyze the more challenging case of homogeneous networks with community structure, for which the Girvan-Newman completely fails in detecting any clustering. The N-ComBa K-means approach performs very well in these situations and we applied it to detect the community structure in an international trade network of miscellaneous manufactures of metal having these characteristics. Some final remarks about the general philosophy of community detection are also discussed.     

Detection of community overlap according to belief propagation and conflict

Most existing methods for detection of community overlap cannot balance efficiency and accuracy for large and densely overlapping networks. To quickly identify overlapping communities for such networks, we propose a new method that uses belief propagation and conflict (PCB) to occupy communities. We first identify triangles with maximal clustering coefficients as seed nodes and sow a new type of belief to the seed nodes. Then the beliefs explore their territory by occupying nodes with high assent ability. The beliefs propagate their strength along the graph to consolidate their territory, and conflict with each other when they encounter the same node simultaneously. Finally, the node membership is judged from the belief vectors. The PCB time complexity is nearly linear and its space complexity is linear. The algorithm was tested in extensive experiments on three real-world social networks and three computer-generated artificial graphs. The experimental results show that PCB is very fast and highly reliable. Tests on real and artificial networks give excellent results compared with three newly proposed overlapping community detection algorithms.     

Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns

The statistical model for community detection is a promising research area in network analysis. Most existing statistical models of community detection are designed for networks with a known type of community structure, but in many practical situations, the types of community structures are unknown. To cope with unknown community structures, diverse types should be considered in one model. We propose a model that incorporates the latent interaction pattern, which is regarded as the basis of constructions of diverse community structures by us. The interaction pattern can parameterize various types of community structures in one model. A collapsed Gibbs sampling inference is proposed to estimate the community assignments and other hyper-parameters. With the Pitman-Yor process as a prior, our model can automatically detect the numbers and sizes of communities without a known type of community structure beforehand. Via Bayesian inference, our model can detect some hidden interaction patterns that offer extra information for network analysis. Experiments on networks with diverse community structures demonstrate that our model outperforms four state-of-the-art models.     

A complex networks approach for data clustering

This work proposes a method for data clustering based on complex networks theory. A data set is represented as a network by considering different metrics to establish the connection between each pair of objects. The clusters are obtained by taking into account five community detection algorithms. The network-based clustering approach is applied in two real-world databases and two sets of artificially generated data. The obtained results suggest that the exponential of the Minkowski distance is the most suitable metric to quantify the similarities between pairs of objects. In addition, the community identification method based on the greedy optimization provides the best cluster solution. We compare the network-based clustering approach with some traditional clustering algorithms and verify that it provides the lowest classification error rate.     

Local affinity in heterogeneous growing networks

In this paper we present a study of the influence of local affinity in heterogeneous preferential attachment (PA) networks. Heterogeneous PA models are a generalization of the Barabási-Albert model to heterogeneous networks, where the affinity between nodes biases the attachment probability of links. Threshold models are a class of heterogeneous PA models where the affinity between nodes is inversely related to the distance between their states. We propose a generalization of threshold models where network nodes have individual affinity functions, which are then combined to yield the affinity of each potential interaction. We analyze the influence of the affinity functions in the topological properties averaged over a network ensemble. The network topology is evaluated through the distributions of connectivity degrees, clustering coefficients and geodesic distances. We show that the relaxation of the criterion of a single global affinity still leads to a reasonable power-law scaling in the connectivity and clustering distributions under a wide spectrum of assumptions. We also show that the richer behavior of the model often exhibits a better agreement with the empirical observations on real networks.     

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.     

A tree-like complex network model

We propose a new tree-like network model. Our results indicate that the tree-like model has a small-world effect with a small average path length and large clustering coefficient. Strikingly, our tree-like model is scale-free. We also add weight to the links following the network structure. With this adding-weight method, the weight of the nodes shows exponential growth, which is ubiquitous in social networks.     

A New Validity Index Based on Fuzzy Energy and Fuzzy Entropy Measures in Fuzzy Clustering Problems

Two well-known drawbacks in fuzzy clustering are the requirement of assigning in advance the number of clusters and random initialization of cluster centers. The quality of the final fuzzy clusters depends heavily on the initial choice of the number of clusters and the initialization of the clusters, then, it is necessary to apply a validity index to measure the compactness and the separability of the final clusters and run the clustering algorithm several times. We propose a new fuzzy C-means algorithm in which a validity index based on the concepts of maximum fuzzy energy and minimum fuzzy entropy is applied to initialize the cluster centers and to find the optimal number of clusters and initial cluster centers in order to obtain a good clustering quality, without increasing time consumption. We test our algorithm on UCI (University of California at Irvine) machine learning classification datasets comparing the results with the ones obtained by using well-known validity indices and variations of fuzzy C-means by using optimization algorithms in the initialization phase. The comparison results show that our algorithm represents an optimal trade-off between the quality of clustering and the time consumption.     

虚拟社区网络的演化过程研究

模拟了虚拟社区网络的演化过程并研究其拓扑结构.发现虚拟社区网络在演化过程中,节点的加入、边的加入、网络中度分布、节点的度与其加入网络时间的关系、平均度随时间的变化等方面与传统的无标度网络有所不符.根据国内某论坛的实际网络数据统计与分析,提出了虚拟社区网络的演化机理——虚拟社区网络构造算法.仿真结果表明,模拟以互联网论坛为代表的虚拟社区网络时,该模型能够得到与真实网络相符的特性. 关键词： 复杂网络 虚拟社区 无标度网络     

Cluster synchronization in networks of distinct groups of maps

In this paper, we study cluster synchronization in general bi-directed networks of nonidentical clusters, where all nodes in the same cluster share an identical map. Based on the transverse stability analysis, we present sufficient conditions for local cluster synchronization of networks. The conditions are composed of two factors: the common inter-cluster coupling, which ensures the existence of an invariant cluster synchronization manifold, and communication between each pair of nodes in the same cluster, which is necessary for chaos synchronization. Consequently, we propose a quantity to measure the cluster synchronizability for a network with respect to the given clusters via a function of the eigenvalues of the Laplacian corresponding to the generalized eigenspace transverse to the cluster synchronization manifold. Then, we discuss the clustering synchronous dynamics and cluster synchronizability for four artificial network models: (i) p-nearest-neighborhood graph; (ii) random clustering graph; (iii) bipartite random graph; (iv) degree-preferred growing clustering network. From these network models, we are to reveal how the intra-cluster and inter-cluster links affect the cluster synchronizability. By numerical examples, we find that for the first model, the cluster synchronizability regularly enhances with the increase of p, yet for the other three models, when the ratio of intra-cluster links and the inter-cluster links reaches certain quantity, the clustering synchronizability reaches maximal.     

Surveying network community structure in the hidden metric space

Most real-world networks from various fields share a universal topological property as community structure. In this paper, we propose a node-similarity based mechanism to explore the formation of modular networks by applying the concept of hidden metric spaces of complex networks. It is demonstrated that network community structure could be formed according to node similarity in the underlying hidden metric space. To clarify this, we generate a set of observed networks using a typical kind of hidden metric space model. By detecting and analyzing corresponding communities both in the observed network and the hidden space, we show that the values of the fitness are rather close, and the assignments of nodes for these two kinds of community structures detected based on the fitness parameter are extremely matching ones. Furthermore, our research also shows that networks with strong clustering tend to display prominent community structures with large values of network modularity and fitness.     

Communities recognition in the Chesapeake Bay ecosystem by dynamical clustering algorithms based on different oscillators systems

We have recently introduced [Phys. Rev. E 75, 045102(R) (2007); AIP Conference Proceedings 965, 2007, p. 323] an efficient method for the detection and identification of modules in complex networks, based on the de-synchronization properties (dynamical clustering) of phase oscillators. In this paper we apply the dynamical clustering tecnique to the identification of communities of marine organisms living in the Chesapeake Bay food web. We show that our algorithm is able to perform a very reliable classification of the real communities existing in this ecosystem by using different kinds of dynamical oscillators. We compare also our results with those of other methods for the detection of community structures in complex networks.     

Personalized PageRank Clustering: A graph clustering algorithm based on random walks

Graph clustering has been an essential part in many methods and thus its accuracy has a significant effect on many applications. In addition, exponential growth of real-world graphs such as social networks, biological networks and electrical circuits demands clustering algorithms with nearly-linear time and space complexity. In this paper we propose Personalized PageRank Clustering (PPC) that employs the inherent cluster exploratory property of random walks to reveal the clusters of a given graph. We combine random walks and modularity to precisely and efficiently reveal the clusters of a graph. PPC is a top-down algorithm so it can reveal inherent clusters of a graph more accurately than other nearly-linear approaches that are mainly bottom-up. It also gives a hierarchy of clusters that is useful in many applications. PPC has a linear time and space complexity and has been superior to most of the available clustering algorithms on many datasets. Furthermore, its top-down approach makes it a flexible solution for clustering problems with different requirements.     

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 mathematical programming approach for sequential clustering of dynamic networks

A common analysis performed on dynamic networks is community structure detection, achallenging problem that aims to track the temporal evolution of network modules. Anemerging area in this field is evolutionary clustering, where thecommunity structure of a network snapshot is identified by taking into account both itscurrent state as well as previous time points. Based on this concept, we have developed amixed integer non-linear programming (MINLP) model, SeqMod, that sequentially clusterseach snapshot of a dynamic network. The modularity metric is used to determine the qualityof community structure of the current snapshot and the historical cost is accounted for byoptimising the number of node pairs co-clustered at the previous time point that remain soin the current snapshot partition. Our method is tested on social networks of interactionsamong high school students, college students and members of the Brazilian Congress. Weshow that, for an adequate parameter setting, our algorithm detects the classes that thesestudents belong more accurately than partitioning each time step individually or bypartitioning the aggregated snapshots. Our method also detects drastic discontinuities ininteraction patterns across network snapshots. Finally, we present comparative resultswith similar community detection methods for time-dependent networks from the literature.Overall, we illustrate the applicability of mathematical programming as a flexible,adaptable and systematic approach for these community detection problems.