There has been a surge of interest in community detection in homogeneous single-relational networks which contain only one type of nodes and edges. However, many real-world systems are naturally described as heterogeneous multi-relational networks which contain multiple types of nodes and edges. In this paper, we propose a new method for detecting communities in such networks. Our method is based on optimizing the composite modularity, which is a new modularity proposed for evaluating partitions of a heterogeneous multi-relational network into communities. Our method is parameter-free, scalable, and suitable for various networks with general structure. We demonstrate that it outperforms the state-of-the-art techniques in detecting pre-planted communities in synthetic networks. Applied to a real-world Digg network, it successfully detects meaningful communities.
A notable issue of modularity optimization is the resolution limit, which refers to the incapability of detecting small communities in large-scale networks @cite_53 @cite_22 . Researchers have tried to get around this issue by proposing variants of modularity. For example, modified modularity by adding a parameter that forms self-loop for each node @cite_33 . Reichardt and Bornholdt modified modularity by adding a parameter in front of the null model term @cite_40 . Both parameters can be used to control the resolution level and detect communities at multiple resolutions. However, a recent study by Lancichinetti and Fortunato demonstrated that these methods are intrinsically deficient and still suffer from the resolution limit @cite_23 .
@cite_22 @cite_33 @cite_53 @cite_40 @cite_23
2061099285 2128366083 2025543856 2095189226
Although widely used in practice, the behavior and accuracy of the popular module identification technique called modularity maximization is not well understood in practical contexts. Here, we present a broad characterization of its performance in such situations. First, we revisit and clarify the resolution limit phenomenon for modularity maximization. Second, we show that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum. Third, we derive the limiting behavior of the maximum modularity Q(max) for one model of infinitely modular networks, showing that it depends strongly both on the size of the network and on the number of modules it contains. Finally, using three real-world metabolic networks as examples, we show that the degenerate solutions can fundamentally disagree on many, but not all, partition properties such as the composition of the largest modules and the distribution of module sizes. These results imply that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts. They also explain why many heuristics are often successful at finding high-scoring partitions in practice and why different heuristics can disagree on the modular structure of the same network. We conclude by discussing avenues for mitigating some of these behaviors, such as combining information from many degenerate solutions or using generative models. Detecting community structure is fundamental for uncovering the links between structure and function in complex networks and for practical applications in many disciplines such as biology and sociology. A popular method now widely used relies on the optimization of a quantity called modularity, which is a quality index for a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. This finding is confirmed through several examples, both in artificial and in real social, biological, and technological networks, where we show that modularity optimization indeed does not resolve a large number of modules. A check of the modules obtained through modularity optimization is thus necessary, and we provide here key elements for the assessment of the reliability of this community detection method. Institute for Theoretical Physics, University of Bremen, Otto-Hahn-Allee, D-28359 Bremen, Germany(Dated: February 3, 2008)Starting from a general ansatz, we show how community detection can be interpreted as ﬁnding theground state of an inﬁnite range spin glass. Our approach applies to weighted and directed networksalike. It contains the at hoc introduced quality function from [1] and the modularity Q as deﬁnedby Newman and Girvan [2] as special cases. The community structure of the network is interpretedas the spin conﬁguration that minimizes the energy of the spin glass with the spin states being thecommunity indices. We elucidate the properties of the ground state conﬁguration to give a concisedeﬁnition of communities as cohesive subgroups in networks that is adaptive to the speciﬁc class ofnetwork under study. Further we show, how hierarchies and overlap in the community structure canbe detected. Computationally eﬀective local update rules for optimization procedures to ﬁnd theground state are given. We show how the ansatz may be used to discover the community around agiven node without detecting all communities in the full network and we give benchmarks for theperformance of this extension. Finally, we give expectation values for the modularity of randomgraphs, which can be used in the assessment of statistical signiﬁcance of community structure. Modularity maximization is the most popular technique for the detection of community structure in graphs. The resolution limit of the method is supposedly solvable with the introduction of modified versions of the measure, with tunable resolution parameters. We show that multiresolution modularity suffers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high. In benchmark networks with heterogeneous distributions of cluster sizes, the simultaneous elimination of both biases is not possible and multiresolution modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter. This holds for other multiresolution techniques and it is likely to be a general problem of methods based on global optimization.