A fast community detection algorithm based on a q-state Potts model is presented. Communities (groups of densely interconnected nodes that are only loosely connected to the rest of the network) are found to coincide with the domains of equal spin value in the minima of a modified Potts spin glass Hamiltonian. Comparing global and local minima of the Hamiltonian allows for the detection of overlapping (''fuzzy'') communities and quantifying the association of nodes with multiple communities as well as the robustness of a community. No prior knowledge of the number of communities has to be assumed. DOI: 10.1103/PhysRevLett.93.218701 PACS numbers: 89.75.Hc, 05.50.+q, 64.60.Cn, 89.65.-s Finding groups of alike elements in data is of great interest in all quantitative sciences. For multivariate data, where the objects are characterized by a vector of attributes, a number of efficient clustering algorithms exist [1] . They allow one to find clusters of similar objects based on a metric between the attribute vectors. If, however, the data are of relational form, e.g., a network GN; M consisting of N nodes and M links connecting them and representing some relation between the nodes, the problem of finding alike elements corresponds to discovering communities: subsets of nodes interconnected more densely among themselves than with the rest of the network (for a recent review see Ref. [2]). This can be formalized as where m is the number of links between the n nodes of the community and m nN is the number of links connecting them to the remaining N ÿ n nodes of the network. In other words, a community's inner link density should be higher than the network's average link density which again should be higher than the community's outer link density. As a community structure we define an assignment of all nodes of the network into communities that fulfill (1). We see from (1) that the presence of communities is bound to the presence of inhomogeneities in the link distribution of a graph. Furthermore, it is understood that a community structure is not defined uniquely on a network. Rather, a number of community structures different in size and number of communities may exist that all fulfill the inequalities (1). Certain nodes may be assigned to different communities in different realizations of community structures. The differences and similarities of these realizations yield valuable information about the robustness of a particular assignment. Furthermore, the nodes which can be placed into more than one community represent an overlap of possible community structures that cannot be interpreted as a hierarchy of communities, since the overlap may be only partial. Here, we introduce a new algorithm that can rapidly detect a community structure and allows for a quantitative assessment of the individual realizations. In this Letter, we combine the early idea by Fu and Anderson for graph bipartitioning with a modified Ising Hamiltonian [3] and the recent Potts model clustering of multivariate data by Blatt et al. [4]. This allows us to map the communities of a network onto the magnetic domains in the ground state or in local minima of a suitable Hamiltonian. For this purpose we alter a q-state Potts Hamiltonian by adding a global constraint that forces the spins into communities according to (1): Here, E is the set of edges, i ; i 1; . . . ; N denote the individual spins which are allowed to take q values 1; . . . ; q, n s denotes the number of spins that have spin s such that P q s1 n s N, J is the ferromagnetic interaction strength, is a positive parameter, and is the Kronecker delta. The first sum is the standard ferromagnetic Potts term for nodes connected by an edge in the network, and is minimized by H ferr ÿJM. It favors a homogeneous distribution of spins over the network. Diversity, on the other hand, is introduced by the second term which sums up all possible pairs of spins which have equal value. It counterbalances the first sum and increases the energy with increasing homogeneity of the spin configuration. It represents a global antiferromagnetic interaction being maximal when all nodes have the same spin, and minimal when all possible spin values are evenly distributed over all nodes. The choice of determines how strongly the minimum of the combined Hamiltonian depends on the topology of the network. Consider a network of two communities g 1 n 1 ; m 1 and g 2 n 2 ; m 2 with m 12 edges connecting them. For the ground state to be composed of these two communities, has to obey a simple condition
Reichardt REF proposed a fast community detection algorithm based on q-state Potts model.
Detecting fuzzy community structures in complex networks with a Potts model.
Physical review letters
Physical review letters
Medicine Physics