Source-linked AI summary
Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
Peter J. Mucha, Thomas Richardson, Kevin Macon, Mason A. Porter, Jukka-Pekka Onnela
TL;DR
Community detection lacks a general framework for multislice networks. This paper develops quality functions using stacked slices and identity arcs, extending modularity-based analysis across temporal, multiplex, and multiscale settings.
Problem
Community detection needs methods that represent networks across multiple slices, link types, and scales.
Method
The paper develops generalized quality functions for multislice networks represented as stacked slices connected by identity arcs.
Results
The framework extends modularity to multislice networks and characterizes properties of quality-optimizing community partitions.
Takeaways & Limitations
The framework supports community-structure analysis for networks that evolve over time, contain multiple link types, or span multiple scales.
Takeaways & Limitations
The analysis includes an independence assumption and, in one optimization argument, assumes a partition is uniquely specified without loss of generality.
Abstract
from arXiv · showhide
Network science is an interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. A prominent problem in network science is the algorithmic detection of tightly-connected groups of nodes known as communities. We developed a generalized framework of network quality functions that allowed us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through links that connect each node in one network slice to itself in other slices. This framework allows one to study community structure in a very general setting encompassing networks that evolve over time, have multiple types of links (multiplexity), and have multiple scales.
Supporting Online Material for Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
The supporting material extends the framework from normalized Laplacian dynamics to bipartite, directed, signed, and multislice networks, while proving convexity of partition-optimization domains for parameter-linear quality functions.
- Framework generalization: The framework generalizes null models from normalized Laplacian dynamics to bipartite, directed, signed, and multislice networks.Multislice networks couple corresponding nodes across slices, and identity arcs support visualization and extensions of measures to dynamic graphs.
- Community-detection methodology: Community detection in multislice networks is derived from community stability under normalized Laplacian dynamics, with a parallel analysis based on unnormalized dynamics.
- Optimization properties: Domains of optimization for each network partition are convex in parameter space when the quality function is linear in those parameters.The supporting material also discusses possible consequences of this convexity result.
Laplacian Dynamics Formalism
The Laplacian dynamics formalism defines community stability through a random walk’s persistence within communities relative to independence, yielding a time-dependent quality function. Its first-order approximation recovers Newman-Girvan modularity at t = 1 and interprets the resolution parameter as γ = 1/t (13).
- Modularity connection: At t = 1, the resulting quality function reduces to Newman-Girvan modularity, while its broader form corresponds to the standard Potts generalization with a resolution parameter (13).This framework derives modularity from continuous-time dynamics and extends the interpretation across timescales.
- Stability definition: Community stability R(t) measures whether a stationary random walker remains within the same community after time t more often than expected under independence (13).The dynamics use L_ij = A_ij/k_j − δ_ij, with the independence contribution appearing in the null-model term.
- Quality function derivation: Expanding e^(tL) to first order makes R(t) yield a community quality function, up to δ_ij terms that do not affect the optimizing partition (13).The approximation is (e^tL)_ij ≈ δ_ij + tL_ij.
- Resolution interpretation: Dividing the quality function by t preserves its optima at fixed t and gives the resolution parameter the direct interpretation γ = 1/t (13).Thus, resolution is interpreted as an inverse dynamical time.
Generalized Laplacian Dynamics
The framework generalizes Laplacian-dynamics community detection by conditioning null models on connection types, allowing multiple link types, spreading weights, and multislice structure. It recovers appropriate bipartite, directed, and signed-network null models and yields a principled multislice modularity.
- Single-slice null models: It recovers generalized null models for bipartite and directed networks by incorporating the resolution parameter γ.The bipartite result generalizes the γ = 1 Barber null model, while the directed result extends standard γ = 1 directed null models.
- Multiple connection types: The method extends Laplacian dynamics to multiple connection types, including bidirectional directed motion and conditional probabilities that respect incoming versus outgoing edges.This contrasts with Lambiotte et al. (13), which restricted motion to link directions.
- Signed networks: Signed-network dynamics produce a null model for positive and negative links, with separate resolution parameters γ+ and γ−.The construction reduces at γ = 1 to one proposed signed null model and is a special case of a more general signed model.
- Flexible spreading weights: The third generalization permits different spreading weights for different link types, yielding the undirected signed model and, combined with earlier extensions, its directed version.This flexibility supports separately reweighted conditional probabilities rather than relying only on relative edge strengths.
- Multislice networks: For multislice networks, the framework combines intra-slice edges with inter-slice couplings and derives modularity using conditional probabilities for both step types.The resulting formulation allows different resolutions γs in each slice and is presented as a principled generalization of modularity to multislice networks.
Unnormalized Multislice Laplacian Dynamics
The framework generalizes the uniform-random-graph quality function derived from standard Laplacian dynamics to multislice networks, using structure-constrained independent probabilities. Its quality function yields independent slice partitions as ω → 0 and slice averaging as ω ≫ 1.
- Null model generalization: The multislice extension uses natural independent probabilities constrained by the network’s multislice structure, generalizing the uniform random null model (5).This builds on the standard-Laplacian community-stability analysis of Lambiotte et al. (13).
- Dynamics: The standard multislice Laplacian has a constant steady-state distribution, jr = 1/N, with node-departure rates proportional to multislice strength κjr.Here, N is the total number of nodes across slices, and κjr = kjr + cjr.
- Quality-function construction: The construction allows distinct resolution parameters within and across slices and absorbs inter-slice coupling strength into binary Cjsr = {0, ω} values.Different weights across couplings can also be considered, and diagonal δijδsr terms do not affect the optimal partition.
- Limiting behavior: As ω → 0, the quality function independently partitions each slice, whereas ω ≫ 1 produces averaging over slices through summed constant contributions.The large-coupling behavior is simpler here than for normalized Laplacian dynamics because the contributions are constant.
Convex Domains of Optimization
For quality functions linear in their parameters, each partition’s optimization domain must be convex: optimality at two parameter points implies optimality along the connecting segment. This result generalizes beyond multislice networks and provides a diagnostic for detecting insufficient optimization.
- Convexity theorem: Linearity in resolution and coupling parameters necessitates convex optimization domains for individual partitions, including for any linear community-detection quality function.The result applies to the generalized multislice quality functions and more broadly to quality functions linear in their parameters.
- Convexity theorem: If one partition is optimal at two parameter points, it must remain optimal throughout the line segment connecting them.This follows from comparing the quality inequalities for distinct partitions at the two endpoints.
- Proof consequence: Beyond the connecting segment, the partition favored at one endpoint is necessarily higher-quality along the corresponding continuation, although neither partition must be optimal there.Therefore, non-convex optimization domains are forbidden for quality functions of the stated linear form.
Examples
This section provides additional details for the three examples discussed in the main text.
- Additional details are provided for the three examples discussed in the main text.
Community Detection Across Multiple Scales
Multislice community detection simultaneously tracked community structure across 16 resolution scales in the Zachary Karate Club network. Increasing inter-slice coupling encouraged communities to span neighboring scales, enabling systematic tracking of multiscale development.
- Multiscale coupling: Increasing coupling between neighboring resolution slices encouraged communities to straddle multiple scales, while arbitrarily large coupling made them span the full resolution range.With only resolution varying across slices, the infinite-coupling limit corresponded to single-resolution detection at the average γ_s≈2.125.
Community Detection in Time-Dependent Networks
Multislice community detection applied to 110 Senate voting-network slices revealed time-dependent individual and group voting dynamics beyond independent congressional partitions. The resulting nine-community structure highlighted historically significant turning points in U.S. politics.
- Community Detection in Time-Dependent Networks: Each two-year Congress formed a network slice with Senator-pair weights based on voting similarity, while consecutive slices coupled Senators only when they served in both Congresses.This formulation allowed both link strengths and the set of nodes to change across slices.
- Community Detection in Time-Dependent Networks: Multislice detection uncovered individual and group voting dynamics over time that the union of 110 independent congressional partitions did not capture.The analysis used a generalized Louvain algorithm plus KL steps with inter-slice coupling ω = 0.5.
- Community Detection in Time-Dependent Networks: A fuller political study would systematically examine how the detected community structure changes as inter-slice coupling strength ω varies.The reported partition used ω = 0.5.
Community Detection in Multiplex Networks · Supplementary References
Multislice community detection was applied to a four-layer social multiplex of 1,640 students, revealing how coupling strength controls whether individuals receive separate or shared community assignments. The framework also supports comparing roles across layers and represents overlapping communities through layer-specific assignments [2,3,S6].
- Community Detection in Multiplex Networks: The multiplex comprised Facebook friendships, picture friendships, shared-roommate ties, and housing-group preferences among 1,640 students during their first university year.The data came from an anonymous northeastern American university [24].
- Community Detection in Multiplex Networks: Because tie types were categorical, each student was coupled to itself across all four layers rather than only to neighboring ordered slices.This inter-slice coupling therefore differs from couplings connecting only adjacent network slices.
- Community Detection in Multiplex Networks: Communities merged most predominantly between layers with relatively similar connection patterns as coupling strength increased.Table 1 summarizes total community counts and the percentages of individuals assigned to 1, 2, 3, or 4 communities across the four layers.
- Community Detection in Multiplex Networks: For ω ∈[0.2, 0.5], a significant majority of individuals belonged to only 1 or 2 communities, indicating group-level similarities across connection types.A significant additional set occupied 3 communities, while a small minority retained 4 assignments, indicating starkly different positions across layers.
- Community Detection in Multiplex Networks: Different assignments across layers can help compare individual roles in each network and in the complete multislice network.The hard partition of each layer-specific node still allows one individual to occupy different communities across appearances.
- Supplementary References: Multiplexity motivates methods that allow communities to overlap [2,3,S6].Layer-specific community assignments provide a mechanism for representing such overlap through differing memberships across an individual's appearances.