Source-linked AI summary
Clique Graphs and Overlapping Communities
T. S. Evans
TL;DR
The paper addresses how to analyze clique structure and overlapping communities without relying solely on vertex-centered representations. It constructs weighted graphs whose vertices represent fixed-order cliques, then applies graph-analysis and community-detection methods to those representations. The examples and benchmark show that clique graphs can recover overlapping community structure, while the approach remains bounded by assumptions such as requiring a simple original graph.
Problem
Vertex-centered analysis and vertex partitions are limited for networks whose community structure is organized around overlapping cliques.
Method
The paper projects fixed-order clique incidence information into weighted clique graphs and applies established vertex-based analyses, including community detection and random-walk measures.
Results
Clique graphs find overlapping communities accurately in the benchmark setting, while vertex partition methods fail.
Takeaways & Limitations
Clique graphs enable existing vertex-partition methods to produce overlapping community structures while placing analytical emphasis on cliques.
Takeaways & Limitations
The original graph G must be simple, although the paper outlines a weighted bipartite extension for handling weighted cliques or edges.
Abstract
from arXiv · showhide
It is shown how to construct a clique graph in which properties of cliques of a fixed order in a given graph are represented by vertices in a weighted graph. Various definitions and motivations for these weights are given. The detection of communities or clusters is used to illustrate how a clique graph may be exploited. In particular a benchmark network is shown where clique graphs find the overlapping communities accurately while vertex partition methods fail.
1. Introduction
The paper challenges a vertex-centric view of networks by representing cliques as vertices in derived graphs, using community detection to demonstrate the approach.
- Motivation: Network analysis commonly emphasizes vertex properties such as degree, clustering coefficient, and vertex partitions.A review of network literature is cited as evidence of the prominence of vertex-related concepts.
- Motivation: Representing cliques as vertices of a derived graph can shift analytical attention away from original-network vertices while retaining standard graph-analysis tools.The transformation is proposed as a way to counterbalance a possible vertex-centric bias.
- Background: Cliques are complete subgraphs with established uses in social-network analysis, graph theory, community detection, and network-growth models.Triads are highlighted as especially relevant to strong ties and relationships.
- Approach: The paper constructs clique graphs and applies vertex-partition methods to them as an example of using clique-centered representations for community detection.This illustrates the paper’s broader principle that derived graphs can enable established vertex-based tools to analyze clique structure.
- Overlapping Communities: Most community-detection algorithms assign each vertex to exactly one community, which is undesirable for networks containing highly overlapping communities.The paper instead hypothesizes that triads can receive community labels while individuals participate in multiple communities.
2. Clique Graphs
The paper constructs several graph projections from fixed-order cliques and their incidence structure, emphasizing weighted clique graphs that preserve overlap information and support community analysis.
- Definitions: For a fixed n ≥ 2, the order-n clique set contains complete subgraphs with n distinct vertices; when n = 2, these cliques are the original graph’s edges.The incidence matrix records whether each original vertex belongs to each order-n clique.
- Incidence Projections: The incidence matrix forms a bipartite graph between original vertices and order-n cliques, while A(n)(G) projects this relation back onto original vertices.In A(n)(G), edge weights count containing order-n cliques, so edges outside such cliques disappear.
- Clique Graphs: The unweighted clique graph L(n)(G) connects two clique vertices when their corresponding cliques share an original vertex, but it loses overlap magnitude.It is equivalent to the line graph of the associated n-uniform hypergraph.
- Weighted Clique Graphs: The weighted graph C(n)(G) assigns each pair of clique vertices a weight equal to the number of original vertices shared by their cliques.Self-loops are excluded, and edge weights range from zero through n − 1.
- Community Detection: Clique percolation corresponds to thresholding C(n)(G) at t = n − 1 and taking connected components, thereby retaining only maximal overlaps.The paper argues that this discards much of the weighted information available for analyzing clique structure.
- Random Walk Motivation: The D(n)(G) and ˜D(n)(G) constructions reduce bias from vertices participating in many cliques, with clique strengths constrained between 1 and n.For ˜D(n)(G), unbiased random walks preserve the dynamics of the original vertex–clique incidence structure, whereas C(n)(G) favors high-k_i^(n) vertices.
3. Overlapping Communities
Partitioning weighted clique graphs represents overlapping communities through clique memberships rather than forcing each original vertex into one group. On the Karate Club, football, and artificial benchmark networks, this approach captures overlaps more faithfully than simple vertex partitioning or clique percolation in settings where those methods are constrained.
- Method: Clique-community partitions assign each original vertex a membership fraction based on the order-n cliques containing it.Vertices can therefore belong to multiple communities, producing a cover rather than a simple partition.
- 3.1. Karate Club: The Karate Club partition of D(3)(G) produces three overlapping communities whose structure reflects the club’s true divisions extremely well.The officers’ group is nearly exclusive, while vertices 2 and 8 receive mixed memberships consistent with their cross-faction ties.
- 3.1. Karate Club: Partitioning C(3)(G) merges the two instructor communities but remains consistent with Zachary’s binary split, with weak overlap concentrated at vertices 2 and 8.Assigning each of those vertices to its largest-overlap community reproduces the original binary partition.
- 3.2. American College Football Network: For the football network, order-four clique methods identify each conference as one community, except for one conference split into its two divisions.Percolation and vertex partitioning of C(4) or D(4) give almost the same structure, with little overlap.
- 3.2. American College Football Network: Order-five clique partitioning places all but one team in the correct conference, but higher orders rapidly fail because such cliques are rarer.Percolation additionally splits one conference into three parts at order five.
- 3.2. American College Football Network: For football triangles, clique-graph vertex partitioning still identifies conferences, whereas percolation produces only four communities and one giant community containing most conference teams.At least 79% of triangles for the affected teams contain only teams from the same conference, making overlap weak and classification accurate.
- 3.3. Benchmark Graph: The standard examples are potentially biased because they come from literature selected for methods that perform well against externally specified vertex partitions.This motivates testing the clique-graph approach on an artificial benchmark designed around overlapping communities.
- 3.3. Benchmark Graph: The artificial benchmark contains twelve intended communities—one per grid row and column—so any vertex partition method necessarily misses at least half the structure.Direct Louvain partitioning usually finds 6 or 7 communities for γ = 0.6 to 2.0, approximating either the rows or the columns.
4. Discussion
The paper shifts network analysis from original vertices to clique-representing vertices in weighted clique graphs, enabling standard graph methods to study clique overlap and overlapping communities. It discusses alternative constructions, extensions to motifs and edge overlap, and limitations including the requirement that the original graph be simple.
- Clique-graph perspective: Clique graphs encode original-graph cliques as vertices, allowing established graph-analysis methods to recover information about clique properties.The transformation moves emphasis onto cliques while retaining vertex-centric analytical tools.
- Clique-graph perspective: This approach differs from prior overlap constructions by placing clique representations at the vertices of a new graph rather than retaining original vertices with overlap-weighted edges.The distinction is the analytical focus: clique vertices instead of original vertices.
- Weighted constructions: Several weighted clique-graph definitions are proposed, with D(n) motivated partly by preserving random-walk dynamics from the bipartite and original graphs.The construction is not unique, and the weighting choice affects how overlap and dynamics are represented.
- Limitations and extensions: The paper’s original graph G must be simple, although weighted bipartite constructions are proposed as a possible route toward weighted extensions.The limitation concerns the input graph setting rather than the general clique-overlap idea.
- Extensions: The constructions can generalize from fixed-order cliques to motifs, directed or signed graph motifs, and edge-overlap representations.Motif examples include n-cliques, n-clans, n-clubs, k-plexes, and k-cores; edge-motif graphs can represent dual-lattice topology.
- Overlapping communities: Clique graphs transform vertex-partition methods into overlapping community detection, but they are generally larger and may incur computational costs.The trade-off depends on graph structure, while fast partitioning may compensate for the larger derived graph.
Appendix A. Alternative Frequency Count
Appendix A presents a frequency table of network-related words from a networks review, ranked by occurrence count with alphabetical ordering for ties.
- Frequency-count procedure: Table A1 lists frequencies of all network-related words in the review, using the original text without alterations.Ranks are based on occurrence counts, with alphabetical order resolving equal counts.
Appendix B.1. Cliques of the Karate Club
The Karate Club graph contains extensive triangle structure alongside a small set of vertices and edges outside order-three cliques, plus higher-order cliques with distinct overlap patterns.
- Clique membership: Vertices 9 and 11 have highest clique order two, while all other vertices belong to order-three cliques.This identifies the two vertices excluded from the graph’s triangle structure.
- Clique membership: All but eleven of the graph’s seventy-eight edges belong to order-three cliques.The eleven excluded edges are explicitly listed in the appendix.
- Order-three structure: The order-three cliques form three percolation clusters, including one isolated three-clique and two larger groups.The isolated clique is {24, 25, 31}; the remaining cliques split into two groups.
- Higher-order cliques: Two order-four cliques are not subgraphs of order-five cliques and do not percolate because they share two rather than three vertices.The cliques are (8, 30, 32, 33) and (23, 29, 32, 33).
- Higher-order cliques: Two order-five cliques percolate around the common four-clique {0, 1, 2, 3}, distinguished by vertices 7 and 13.The two order-five cliques share the common order-four clique.
- Community analysis: The number of detected communities is examined as γ varies for the C(3) and D(3) clique graphs.Figure B1 compares the two clique-graph constructions using blue dotted and red dashed lines.
Appendix B.2. Communities of the Karate Club
Appendix B.2 compares Karate Club community structures obtained from vertex partitions and from clique-graph partitions, with γ = 0.5 producing stable clique-community results.
- Community comparison: For D(3)(G), γ = 0.5 yields three clique communities that closely correspond to a Louvain vertex partition at γ = 0.3 and Zachary’s binary split.The appendix describes this correspondence as fully consistent with the binary split.
- Reference partitions: The appendix includes Zachary’s binary partition and the vertex partition producing the largest modularity Q(A).These provide comparison structures for the overlapping community results.
- Clique-graph partitions: Tables B3 and B4 report overlapping community structures obtained by partitioning C(3)(G) and D(3)(G), respectively, with Louvain at γ = 0.5.Non-trivial membership fractions are shown in brackets after vertex indices.
- Figure B2: Figure B2 shows two communities of order-three cliques in the Karate Club using modularity optimization on weighted C(3)(G) with γ = 0.5.Red marks indicate vertices or an edge belonging to order-three cliques from different communities, while grey marks indicate elements in no order-three clique.
Appendix C.1. Clique description
For the football network, clique-based community detection depends strongly on clique order and representation. Order-four methods best match conference structure, while order-three and higher-order percolation show distinct failures or limits.
- Order-three cliques: Order-three clique percolation identifies only four communities, placing most remaining conference teams in one giant community.
- Order-three cliques: Vertex partitioning of C(3) places about two-thirds of conference teams in conference-specific communities, while the remaining overlap is mostly weak.
- Order-four cliques: Order-four clique percolation detects all conferences except one split into two divisions, with limited additional overlap involving independent teams.
- Order-four cliques: The D(4) vertex partition reproduces the order-four percolation structure except that it assigns one community per conference without splitting conferences.
- Order-four cliques: The C(4) vertex partition also closely matches the conference structure.
- Higher-order cliques: For order-five percolation, 15 communities remain within the 11 conferences, but higher orders leave too few teams in cliques and increasingly miss conferences.
Appendix C.2. Data Sources
The football network represents every Division I-A game played during Fall 2000 as an edge. The authors simplified duplicate-game edges and corrected conference assignments to reflect the 2000 season.
- Network construction: The dataset contains one edge for every game between Division I-A American College Football teams during Fall 2000.
- Network construction: Duplicate games between three team pairs were reduced to single edges so the resulting graph is simple.
- Conference assignments: Conference labels were revised because the source assignments appeared to reflect the 2001 season rather than Fall 2000.
- Conference assignments: The corrected conference table lists the Fall 2000 conferences and supplies the indices used in the network figures.
- Conference assignments: Additional corrections reassigned specific teams among Big West, Western Athletic, Independent, and other conference categories.
- Validation: A sample of games was checked against the College Football Data Warehouse and Wikipedia conference and team entries.
Appendix D. Further Benchmark example
On the benchmark graph, clique-graph partitions recover both overlapping row and column communities more completely than ordinary vertex or weighted-line-graph partitions.
- Benchmark comparison: The ordinary vertex partition finds six column communities but completely misses the row communities.
- Clique-graph partitions: The D(3) clique-graph partition produces 12 communities matching the benchmark’s row and column communities, with one column split across two communities.
- Clique-graph partitions: The C(3) clique-graph partition also finds 12 communities matching the row and column communities perfectly.
- Benchmark comparison: The weighted line-graph edge partition finds the six columns and one row community, whereas the corresponding vertex partition misses the row communities.