PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantifying and identifying the overlapping community structure in networks

Hua-Wei Shen, Xue-Qi Cheng, Jia-Feng Guo

arXiv:0905.2666v2physics.soc-ph

TL;DR

Traditional modularity-based methods cannot quantify overlapping community structure. The paper proposes Qc and a maximal-clique-network partitioning approach; it reports high Qc for networks with significant overlap and strong benchmark variation-of-information results when µ < 0.5.

  • Problem

    Traditional modularity-based methods cannot handle overlapping community structure, where a node may belong to more than one community.

    Source: §I · p. 1

  • Method

    Qc assigns each maximal clique to one community, and its optimization is equivalent to modularity optimization on a constructed maximal clique network.

    Source: §I · p. 2, C. Discussions · p. 5

  • Results

    Networks with significant overlap have high Qc; for benchmarks with µ < 0.5, variation of information exceeds 0.8 for k = 4, 5, 6.

    Source: A. Tests on artificial networks · p. 6, §IV · p. 8

  • Takeaways & Limitations

    Iteratively applying the method within communities can identify a rigid hierarchy of overlapping communities.

    Source: C. Discussions · p. 5

Abstract

from arXiv · show

It has been shown that the communities of complex networks often overlap with each other. However, there is no effective method to quantify the overlapping community structure. In this paper, we propose a metric to address this problem. Instead of assuming that one node can only belong to one community, our metric assumes that a maximal clique only belongs to one community. In this way, the overlaps between communities are allowed. To identify the overlapping community structure, we construct a maximal clique network from the original network, and prove that the optimization of our metric on the original network is equivalent to the optimization of Newman's modularity on the maximal clique network. Thus the overlapping community structure can be identified through partitioning the maximal clique network using any modularity optimization method. The effectiveness of our metric is demonstrated by extensive tests on both the artificial networks and the real world networks with known community structure. The application to the word association network also reproduces excellent results.

I. INTRODUCTION

Community structure captures groups of densely connected nodes, but traditional modularity-based methods cannot represent communities that overlap. The paper introduces Qc, a cover-quality measure based on assigning maximal cliques to communities, and proposes identifying covers by partitioning a maximal clique network.

I. INTRODUCTION

  • Traditional modularity-based methods require each node to belong to one community and cannot handle overlapping community structure.Modularity also has a resolution-limit problem.Source: §I · p. 1
  • Prior approaches include k-clique percolation, belonging-coefficient modularity, and line-graph partitioning, each with stated limitations.The cited discussion notes incomplete covers and difficulty revealing hierarchy for k-clique methods, unclear coefficient meaning and scalability concerns, and line-graph overlaps restricted to nodes.Source: §I · pp. 1–2
  • Qc quantifies overlapping community structure by evaluating the quality of a network cover.An optimal cover is the one with maximum Qc.Source: §I · p. 2
  • The method assumes each maximal clique belongs to one community, allowing nodes to belong to overlapping communities.A maximal clique is a complete subgraph that is not a subset of another clique.Source: §I · p. 2

II. THE QUANTIFYING AND IDENTIFYING METHODS

  • The paper proposes constructing a maximal clique network and identifying overlaps by partitioning it with a modularity optimization algorithm.The authors prove that optimizing Qc on the original network is equivalent to optimizing modularity on the maximal clique network.Source: §I · p. 2, §II · p. 2

A. Quantifying the overlapping community structure

Qc extends modularity to quantify covers in which nodes may belong to multiple communities. It defines belonging coefficients using the maximal-clique view, under the assumption that each maximal clique belongs to only one community.

A. Quantifying the overlapping community structure

  • A belonging coefficient α_vc extends the partition indicator to express how much vertex v belongs to community c.The coefficient is proportional to the total weight of edges connecting v to vertices in c.Source: A. Quantifying the overlapping… · pp. 2–3
  • Additivity defines a community’s belonging coefficient as the sum of the coefficients for its subcommunities, reducing the solution space.The general constraints alone leave an impractically large space to enumerate.Source: A. Quantifying the overlapping… · p. 2
  • The additivity property requires a maximal-clique view, where each maximal clique belongs to one community.The authors motivate this assumption by the high connectivity of maximal cliques: communities sharing one should be combined.Source: A. Quantifying the overlapping… · p. 3
  • Qc measures the quality of a cover, and reduces to modularity when the cover is a partition.Qc is zero when all vertices belong to the same community; the paper states that high Qc indicates significant overlapping structure.Source: A. Quantifying the overlapping… · pp. 2–3

B. Identifying the overlapping community structure

An optimal cover maximizes Qc. The paper constructs a maximal clique network from the original network and identifies the overlapping structure by partitioning that network.

B. Identifying the overlapping community structure

1. Construction of the maximal clique network

The maximal clique network represents each sufficiently large maximal clique and each remaining subordinate vertex as a node, with edge weights derived from belonging coefficients. Its partitions can map back to covers of the original network, preserving overlap.

1. Construction of the maximal clique network

  • Maximal cliques of size at least k and vertices belonging only to smaller maximal cliques become nodes of G′; k controls which cliques are retained.The smaller cliques are termed subordinate maximal cliques, and their otherwise-unrepresented vertices are subordinate vertices.Source: §1 · p. 3
  • Subordinate vertices have belonging coefficient 1 for their own cluster and 0 for others; other coefficients follow equation (7).Figure 2 illustrates the cover, coefficients, and resulting network for k = 3.Source: §1 · p. 3, Figure 2 · p. 4
  • The weight B_xy between nodes of G′ is defined from the original vertices represented by those nodes and their belonging coefficients.For the example edge between nodes a and b, equation (9) gives weight 2.5.Source: §1 · pp. 3–4
  • The total edge weight L′ of G′ equals the original network’s edge count L, and a partition of G′ maps to a cover of the original network.An original vertex may correspond to multiple nodes in G′, carrying overlap information into the cover.Source: §1 · p. 4

2. Finding the overlapping community structure

The method finds an overlapping cover by partitioning the maximal clique network. The paper proves that maximizing modularity on that network is equivalent to maximizing Qc on the original network.

2. Finding the overlapping community structure

  • The method partitions the maximal clique network using the modularity-optimization algorithm proposed in.The optimal partition is the one with maximum modularity; Figure 3 depicts an example partition and its corresponding communities.Source: §2 · p. 4, Figure 3 · p. 5
  • Each partition of the maximal clique network corresponds to a cover of the original network, and the paper examines whether their optima correspond.The proof relates the partition modularity to Qc for the corresponding cover.Source: §2 · pp. 4–5
  • Maximizing Qc on the original network is equivalent to maximizing modularity on its maximal clique network, so the latter’s optimal partition gives the optimal cover.That cover represents the original network’s overlapping community structure.Source: §2 · p. 5

C. Discussions

The method’s overlap structure depends on k, while Qc retains modularity’s resolution limit. The paper also discusses computational efficiency and iterative recovery of hierarchical communities.

C. Discussions

  • As k increases, fewer vertices can occur in overlapping regions; when k →∞, the method identifies no overlap.The authors say k should not be too small, give 3–6 as a typical range in many real-world networks, and note rare overlaps when large cliques are rare.Source: C. Discussions · p. 5
  • Qc has the resolution-limit problem, especially on large networks, and methods proposed to address modularity’s limit also apply to Qc.The paper states that Qc shares this limitation with traditional modularity.Source: C. Discussions · p. 5
  • The method has three stages—finding maximal cliques, constructing G′, and partitioning it—and the authors describe it as very efficient on real-world networks.They note maximal-clique finding is widely believed to be non-polynomial, but easy on sparse real-world networks; later-stage costs depend on edge and node counts.Source: C. Discussions · p. 5
  • Applying the method iteratively to each community can identify a rigid hierarchy of overlapping communities across the network.The hierarchy is obtained by repeating the Qc optimization within communities.Source: C. Discussions · p. 5

III. RESULTS

The results section describes tests on artificial and real-world networks with known community structure, followed by an application to a large real-world network with overlapping communities.

III. RESULTS

  • The evaluation covers artificial and real-world networks with known community structure, then applies the method to a large real-world network reported to have overlapping communities.The passage describes the evaluation scope but does not state its outcomes.Source: §III · p. 6

A. Tests on artificial networks

On benchmark networks with overlapping communities, the method performs well when community fuzziness is low. The evaluation compares its detected covers with the known covers using an extension of variation of information.

A. Tests on artificial networks

  • The benchmark varies community fuzziness using µ, with default networks of 1,000 nodes, average degree 15, and 50 overlapping nodes with two memberships each.It also accommodates heterogeneous degree and community-size distributions; larger µ means fuzzier communities.Source: A. Tests on artificial networks · p. 6
  • The evaluation adopts a cover-comparison measure that extends variation of information, with higher values indicating more similar covers.The measure compares the detected cover with the benchmark's known overlapping community structure.Source: A. Tests on artificial networks · p. 6
  • For µ below 0.5, variation-of-information values exceed 0.8 for k = 4, 5, and 6; results are similar for k above 6.These benchmark cases have strong communities, where each node has more neighbors in its own community than in others.Source: A. Tests on artificial networks · p. 6

B. Tests on real world networks

Tests on the karate club and dolphin networks show that the method recovers known divisions while also identifying overlapping memberships at k = 3. At k = 4, the karate partition makes no vertex errors, and the dolphin communities reveal additional structure.

B. Tests on real world networks

  • At k = 4, the karate partition has modularity 0.417 versus 0.371 for the real two-group split, yet no vertex is misclassified and pairwise merging recovers that split.The method initially finds four communities.Source: B. Tests on real world networks · pp. 6–7
  • At k = 3, the karate cover has Qc = 0.385 and three overlapping communities sharing vertices 1, 3, and 9; other vertices reflect the real split.No overlaps appear for k of at least 4 in this network.Source: B. Tests on real world networks · p. 7
  • For the dolphins, four communities at k = 4 recover the known division when the three circle groups are treated as one, while also revealing a further split correlated with gender.The blue group is mainly female, and the other two circle groups are almost entirely male.Source: B. Tests on real world networks · p. 7
  • At k = 3, dolphin overlaps emerge among the circle communities while the green community stays almost intact; Qc is 0.490, and Beak and Kringel belong to all three circle groups.No overlaps appear for k of at least 4 in this network.Source: B. Tests on real world networks · p. 7

C. Application to the word association network

The method finds overlapping communities in the word-association network and applies it iteratively to examine their hierarchy. In the communities around “play,” distinct word senses and shared words illustrate both local overlap and broader relationships between communities.

C. Application to the word association network

IV. CONCLUSIONS

Qc quantifies overlapping community structure, and the method identifies it by partitioning a maximal clique network with modularity optimization. The paper also describes Qc’s scope and directions for further work.

  • Networks with significant overlapping community structure have covers with high Qc, supporting the measure’s effectiveness.Source: §IV · p. 8
  • The method constructs a maximal clique network and identifies overlapping communities by applying any modularity-optimization method to it.Source: §IV · pp. 8–9
  • Qc extends modularity by assigning community exclusivity to maximal cliques, combining local clique topology with global link-density significance against a null model.The paper also states that Qc can simultaneously identify overlapping and hierarchical community structure.Source: §IV · p. 9
  • Future work includes generalizing the method to weighted or directed networks and investigating how to choose parameter k.Source: §IV · p. 9
Loading 0905.2666v2…