PaperlayerView exact revision on arXiv

Source-linked AI summary

Line Graphs, Link Partitions and Overlapping Communities

T. S. Evans, R. Lambiotte

arXiv:0903.2181v2physics.soc-phphysics.data-an

TL;DR

Node partitioning forces each node into one community, limiting representation of overlapping structure. The paper partitions links by applying node-partition methods to the original network’s line graph, and shows meaningful overlapping communities while addressing degree heterogeneity with weighting.

  • Problem

    Node-based community detection assigns each node to one community, although social and scientific networks can contain overlapping communities at individuals.

  • Method

    The paper partitions links into communities through node partitioning of the original network’s line graph, using weighted versions to account for high-degree nodes.

  • Results

    Q(C)=0.1, Q(D)=0.278, and Q(E1)=0.167 recover the expected two-triangle link partition in the Bow Tie graph.

  • Takeaways & Limitations

    Link partitioning naturally allows nodes to belong to multiple communities while retaining established graph-analysis techniques.

Abstract

from arXiv · show

In this paper, we use a partition of the links of a network in order to uncover its community structure. This approach allows for communities to overlap at nodes, so that nodes may be in more than one community. We do this by making a node partition of the line graph of the original network. In this way we show that any algorithm which produces a partition of nodes can be used to produce a partition of links. We discuss the role of the degree heterogeneity and propose a weighted version of the line graph in order to account for this.

I. INTRODUCTION

Traditional community detection partitions nodes into exclusive communities, limiting its fit for overlapping networks. The paper instead partitions links, allowing nodes connected to multiple link communities to belong to multiple communities.

  • Motivation: Most community detection methods partition nodes so each node belongs to exactly one community.Modularity evaluates within-community links against a degree-preserving random-graph expectation.
  • Motivation: Exclusive node membership is undesirable for networks whose social or scientific communities overlap at individuals.Inter-community individuals can connect otherwise separated contacts and different interests.
  • Link-partition approach: Partitioning links lets a node belong to several communities when its incident links belong to different link groups.The paper illustrates this with the central node of a Bow Tie graph.
  • Link-partition approach: The approach is especially suited to heterogeneous nodes connected by relatively homogeneous link types, such as social networks with minimally overlapping friendship and work links.The paper positions link partitioning as one of few approaches proposed for overlapping node communities.
  • Paper plan: The paper derives modularities for link partitions using dynamical processes on links and connections to line graphs, then optimizes them on example networks.The stated workflow covers dynamical processes, line-graph and bipartite-projection connections, and example applications.

II. DYNAMICAL FORMULATION OF MODULARITY

The paper interprets modularity through random-walk persistence within communities and generalizes it to walks of arbitrary length. This dynamical perspective motivates analogous processes on links for evaluating link partitions.

  • Dynamical interpretation: Usual modularity can be interpreted as the difference between within-community persistence of one random walker and coincident occupancy by independent walkers.The interpretation is formed by comparing successive-step and independent-walker probabilities for each community.
  • Resolution: Stability R(A, n) generalizes modularity from one-step paths to paths of arbitrary length, enabling resolution control through walk duration.Increasing n typically yields larger communities, with the asymptotic optimum consisting of two communities.
  • Dynamical interpretation: The node random walk uses transition probabilities T_ij = A_ij/k_j, with stationary node density proportional to degree under the stated graph assumptions.The analysis assumes undirected, connected, non-bipartite, simple networks.
  • Link dynamics: Figure 2 contrasts a link-link walk that jumps uniformly among adjacent links with a link-node-link walk that chooses a node first and then an incident new link.Both processes place walkers on links, but they differ in how transitions through shared nodes are selected.

III. LINK PARTITION

The paper defines two random walks on links whose transition rules differ in how they pass through a link’s endpoint nodes. Degree heterogeneity separates the processes and motivates accounting for endpoint degrees.

  • Link-link random walk: The link-link walk jumps uniformly among links leaving either endpoint, using probability 1/(k_i + k_j − 2) for each available link.When endpoint degrees differ, this rule gives unequal total passage probabilities through the two endpoints.
  • Link-node-link random walk: The link-node-link walk chooses one endpoint with probability one-half, then chooses uniformly among that endpoint’s incident links excluding the link just traversed.For a leaf endpoint, the process instead moves through the other endpoint among its available links.
  • Degree heterogeneity: The two walks coincide when endpoint degrees are equal on every link, which in a connected graph is equivalent to regularity.Otherwise, the link-link walk favors passage through the higher-degree endpoint.

B. Projecting the incidence matrix

The incidence matrix represents a network as a bipartite graph, whose projection onto links produces the line graph and a link-based random-walk quality function. Because high-degree nodes generate large cliques in the unweighted line graph, the paper motivates degree-aware weighting.

  • B. Projecting the incidence matrix: The incidence matrix B is an N × L bipartite representation connecting original nodes to links.Its two vertex types are the nodes and links of the original graph.
  • B. Projecting the incidence matrix: Projecting the incidence graph onto its link vertices produces an L × L adjacency matrix C for the line graph.Two projected link-vertices are adjacent when their original links share a node.
  • B. Projecting the incidence matrix: In the unweighted line graph, each original node of degree k_i becomes a fully connected clique of k_i links.The resulting graph has O(⟨k^2⟩N) links, and its structure generally preserves the original graph except for triangles and four-node stars.
  • B. Projecting the incidence matrix: The link-link random walk depends on the sum of the degrees at a link’s two endpoints, with its stationary distribution defined over links.The corresponding quality function is obtained by applying the modularity derivation to the projected graph.
  • B. Projecting the incidence matrix: A degree-k_i node creates a clique of k_i(k_i −1)/2 links, potentially overemphasising high-degree nodes in the unweighted line graph.The proposed response is a weighted line graph whose link weights scale as O(1/k_i).

3. Weighted line graph

The weighted line graph normalizes link–link connections by the degree of their shared original node, producing a representation aligned with link–node–link dynamics. Its weighted degrees are nearly uniform, unlike the unweighted construction except for regular graphs.

  • 3. Weighted line graph: The weighted line graph D(G) is constructed by projecting the incidence matrix with a degree-dependent normalization.The normalization is based on the degree k_i of the shared original node.
  • 3. Weighted line graph: The weighted degree of a link is two unless it is a leaf, whose weighted degree is one except in one trivial case.Thus the construction reflects that each original link has two endpoints.
  • 3. Weighted line graph: The weighted line graph D(G) is equivalent to the unweighted line graph L(G), up to an overall scale, only when the original graph is regular.For collaboration networks, the same normalization makes links associated through larger author groups less connected.
  • 3. Weighted line graph: The weighted line graph provides the natural state space for the link–node–link random walk and yields a corresponding link-partition quality function.Its total weighted degree is 2L − L_leaf, where L_leaf is the number of leaves.

C. Projection of a node random walk

The paper also projects the original node random walk onto links, using weighted line graphs with self-loops. This construction leads to a link-partition modularity that is equivalent to ordinary node modularity under a different membership constraint.

  • C. Projection of a node random walk: Line-graph random walks differ from the original node walk because link walkers may pass through the same original node at consecutive steps.This motivates projecting the node-driven process onto links instead.
  • C. Projection of a node random walk: The graph E(G) represents an unbiased two-step walk on the incidence graph and includes self-loops, with every link-node having strength two.The self-loops account for the two ends of each original link.
  • C. Projection of a node random walk: Applying the original node walk to E(G) produces E1 = EE − E, another weighted graph with self-loops and strength two at every link-node.The associated quality function is defined for partitions of the original links.
  • C. Projection of a node random walk: An alternative unweighted line graph with self-loops differs from L(G) only by adding one self-loop to every line-graph node.This modification can be interpreted as a mechanism for controlling the number and size of detected communities.
  • C. Projection of a node random walk: Optimizing modularity on E1 is equivalent to optimizing the original graph’s modularity with a different constraint on node community memberships.The link memberships are converted into node memberships using the incidence matrix.

A. Methodology

The methodology defines link partitions through random-walk-based quality functions and evaluates them on a Bow Tie graph. The resulting link communities overlap at the central node, unlike a node partition.

  • A. Methodology: The paper defines three quality functions, Q(C), Q(D), and Q(E1), for link partitions associated with different dynamical processes.Their stability versions extend modularity to paths of arbitrary length for resolution control.
  • A. Methodology: On the Bow Tie graph, optimizing all three functions recovers the expected partition into two triangles.The reported values are Q(C)=0.1, Q(D)=0.278, and Q(E1)=0.167.
  • A. Methodology: The central Bow Tie node belongs equally to both link communities, while the best node partition assigns it to only one community.The best node partition is described as three nodes in one triangle and two nodes in the other.
  • A. Methodology: A boundary node in a link partition is incident to links from more than one link community.The central node of the Bow Tie is the paper’s example of such a boundary node.

B. Karate Club

Karate Club experiments show that link partitions recover the historical two-way split while revealing structure that depends on the chosen dynamical process and resolution.

  • Node partitions: The node partition with maximal modularity has four communities, whereas increasing stability resolution produces two communities matching Zachary’s historical split.The two-community result occurs for sufficiently large n; R(A, 11) = 0.078 matches the sink/source partition.
  • Link partitions: Optimising Q(C), Q(D), and Q(E1) yields link partitions with 4, 7, and 3 communities, respectively.Their quality values are Q(C) = 0.5, Q(D) = 0.53, and Q(E1) = 0.36.
  • Link partitions: All three optimal link partitions are consistent with the historical split because its boundary links connect to boundary nodes in each link partition.The partitions nevertheless differ substantially because they represent different dynamical processes.
  • Process dependence: Around node 1, Q(D) and Q(E1) identify a bridging position, while Q(C) makes node 1 the focus of a link community.The difference is attributed to node 1’s high degree, which biases the link-link random walk through it.
  • Resolution tuning: Increasing the walk length n produces larger communities and eventually a two-way link partition that perfectly matches the node partition.This resolution tuning is demonstrated using the weighted line graph D and stability R(D, n).

C. Word Associations

The word-association example applies weighted line-graph modularity to uncover overlapping communities around “bright,” spanning both clique-like and tree-like structures.

  • Network construction: Scaling the null-model factor by 10.0 yields 321 communities in the full word-association network.The network contains 5018 words and 58536 links, and its line graph contains 1266910 links.
  • Overlapping communities: The word “bright” belongs to eleven communities, illustrating overlap in the link-partition representation.The displayed subgraph retains nodes having at least 90% of their links in one connected community.
  • Community structure: The detected communities range from tight clique-like subsets, such as planet names, to tree-like sequences such as “lit-on-switch-lever-handle.”This flexibility is less constrained than k-clique percolation.
  • Membership strength: “Bright” has sixteen of twenty-nine links in the community containing “sunshine” and “light,” but only one link to eight of its eleven communities.This uneven link distribution motivates viewing link counts as a strength of membership.
  • Membership strength: The visualization keeps words with many links within one community to make overlapping membership easier to interpret.Many words otherwise belong to several communities with only one or two links per community.

V. DISCUSSION

The paper argues that link partitioning offers a natural way to represent overlapping communities while retaining access to established node-partitioning methods through line graphs. It also extends the framework to weighted networks and relates it to two-clique percolation.

  • V. DISCUSSION: Link partitioning overcomes the constraint that each node belongs to only one community, allowing nodes to participate in multiple link-defined communities.This is particularly relevant when links represent different types of relationships.
  • V. DISCUSSION: A link partition of G is equivalent to a node partition of its line graph L(G), so existing node-partitioning code can be reused.Explicitly constructing the line graph increases memory by O(⟨k2⟩/⟨k⟩), but the equivalent process on G can reduce the additional memory cost to O(1).
  • V. DISCUSSION: The method generalises k-clique percolation by identifying densely connected collections of two-cliques rather than only connected components.The authors describe this as an extension that can uncover finer modules.
  • V. DISCUSSION: The framework applies to weighted networks and can accommodate multiedges when formulated from the incidence matrix.The approach can also support graph analyses beyond community detection by applying them to a line graph representation.
Loading 0903.2181v2…