PaperlayerView exact revision on arXiv

Source-linked AI summary

A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks

Marya Bazzi, Lucas G. S. Jeub, Alex Arenas, Sam D. Howison, Mason A. Porter

arXiv:1608.06196v5cs.SIcond-mat.stat-mechnlin.AOphysics.soc-phstat.ME

TL;DR

Existing multilayer mesoscale models restrict or leave unspecified the dependencies they can represent. This framework separates partition generation from edge generation and explicitly specifies interlayer dependencies. It encompasses temporal, multiplex, and multi-aspect networks and supports synthetic-network generation and detectability studies.

  • Problem

    Existing multilayer mesoscale models allow only restrictive interlayer dependencies or do not explicitly specify them.

    Source: C. Generative models for mesoscale… · p. 5

  • Method

    The framework separately generates partitions and edges and uses an explicitly parametrizable tensor to control interlayer-dependency structure.

    Source: §VII · p. 19

  • Results

    The framework covers temporal, multiplex, multilevel, and multi-aspect networks with uniform or nonuniform dependencies between state nodes.

    Source: §VII · p. 19

  • Takeaways & Limitations

    The framework can generate synthetic and null networks and explore mesoscale detectability limits; statistical-inference models require further work.

    Source: A unifying framework · p. 2

    The numerical examples focus on a few special cases and on community structure, although the framework can also model other mesoscale structures.

    Source: §VII · p. 19

Abstract

from arXiv · show

Multilayer networks allow one to represent diverse and coupled connectivity patterns --- e.g., time-dependence, multiple subsystems, or both --- that arise in many applications and which are difficult or awkward to incorporate into standard network representations. In the study of multilayer networks, it is important to investigate mesoscale (i.e., intermediate-scale) structures, such as dense sets of nodes known as communities, to discover network features that are not apparent at the microscale or the macroscale. The ill-defined nature of mesoscale structure and its ubiquity in empirical networks make it crucial to develop generative models that can produce the features that one encounters in empirical networks. Key purposes of such generative models include generating synthetic networks with empirical properties of interest, benchmarking mesoscale-detection methods and algorithms, and inferring structure in empirical multilayer networks. In this paper, we introduce a framework for the construction of generative models for mesoscale structures in multilayer networks. Our framework provides a standardized set of generative models, together with an associated set of principles from which they are derived, for studies of mesoscale structures in multilayer networks. It unifies and generalizes many existing models for mesoscale structures in fully-ordered (e.g., temporal) and unordered (e.g., multiplex) multilayer networks. One can also use it to construct generative models for mesoscale structures in partially-ordered multilayer networks (e.g., networks that are both temporal and multiplex). Our framework has the ability to produce many features of empirical multilayer networks, and it explicitly incorporates a user-specified dependency structure between layers.

I. INTRODUCTION

Multilayer networks represent changing or multiple interaction patterns and dependencies that single-layer representations cannot capture. The paper presents a flexible framework for generating mesoscale structure across multilayer settings.

I. INTRODUCTION

  • Temporal and multiplex networks capture changing connections and multiple interaction types, while multilayer representations can also model dependencies between layers.The framework is intended to support synthetic-network generation, benchmarking mesoscale-detection methods, and inference on empirical networks.Source: §I · pp. 1–2

A unifying framework

  • The framework separates partition generation from edge generation and supports varied interlayer dependencies and network features.Users can pair a specified dependency structure with any planted-partition network model to generate features such as weighted, directed, or spatially embedded edges.Source: A unifying framework · p. 2, §I · p. 2

A. Multilayer networks

  • A multilayer network represents entities across states defined by aspects, which may be ordered, such as time, or unordered, such as platform.A state node is an instance of a physical node in a particular state; networks may combine multiple aspects.Source: A. Multilayer networks · p. 3

B. Mesoscale structures in networks

  • Mesoscale structures lie between microscale and macroscale features and include communities, core–periphery structure, and role structure.A multilayer community can include state nodes from different layers, and its induced communities may depend on connectivity in other layers.Source: B. Mesoscale structures in networks · p. 4

C. Generative models for mesoscale structure

Existing multilayer mesoscale models often restrict which interlayer dependencies they represent. The paper motivates a more general partition-generation approach that specifies dependencies flexibly while addressing conditional-model compatibility and sampling.

C. Generative models for mesoscale structure

  • Existing models restrict interlayer dependencies to particular temporal, multiplex, or grouped-layer patterns, or leave them unspecified.The framework instead makes dependencies explicitly specifiable.Source: C. Generative models for mesoscale… · p. 5

III. NOTATION

  • A multilayer partition divides state nodes into meso-sets and induces a partition on each layer.A meso-set can represent any mesoscale structure; a community is a meso-set corresponding specifically to community structure.Source: §III · pp. 5–6

IV. GENERATING MULTILAYER PARTITIONS

  • Conditional distributions may be incompatible, but the partition-generation process is designed to remain well-defined and guarantee convergence.The framework also addresses non-uniqueness by sampling initial conditions and suggests empirical checks of planted dependencies.Source: §IV · p. 6
  • The framework separates independent layer-specific null distributions from a user-specified tensor that encodes direct interlayer dependencies.Null distributions govern possible assignments and expected meso-set sizes and counts without interlayer dependencies; the tensor can specify dependencies at the state-node or layer level.Source: §IV · p. 6
  • The update process samples assignments by drawing from null distributions or copying another state node’s assignment, with strategies adapted to network ordering.Fully ordered networks use sequential layer sampling, unordered networks use a Markov chain and pseudo-Gibbs sampling, and partially ordered networks combine these strategies.Source: §IV · p. 7

A. Null distribution

Layer-specific null distributions set the baseline meso-set assignments, while an interlayer-dependency tensor controls how assignments can copy across layers. The sampling process also depends on update and initialization choices.

A. Null distribution

  • Categorical null distributions set the probability of each meso-set label in each layer, controlling expected meso-set numbers and sizes without interlayer dependencies.Dirichlet-sampled probabilities can produce equally sized meso-sets or a few large and many small ones; sampling the support can model meso-set birth or death across layers.Source: A. Null distribution · p. 7

B. General interlayer dependencies

  • The interlayer-dependency tensor assigns copying probabilities between state nodes, defining direct dependencies and the associated information-flow network.A state node’s null distribution supplies possible assignments when it does not copy from an in-neighbor.Source: B. General interlayer dependencies · pp. 7–8
  • A sampled partition depends on the assignment-update rule, update order, initial partition, and convergence criterion.The paper discusses update and initialization choices in this subsection and treats convergence in Appendix B.Source: B. General interlayer dependencies · p. 8

Update equation

The framework updates each state node’s meso-set assignment by copying from dependent layers or sampling from a layer-specific null distribution. It orders and samples updates to respect ordered aspects, and a layer-coupled restriction covers temporal, multiplex, and multi-aspect dependencies.

Update equation

  • Each update copies a state node’s meso-set assignment from an in-neighbor with probability ˆp_j,β, or draws from the layer’s null distribution with probability 1 − ˆp_j,β.The null distributions specify assignments without interlayer dependencies; the copying probability controls their relative importance.Source: Update equation · p. 8

Update order

  • For ordered aspects, dependency edges and update order must respect the aspect’s ordering, so preceding layers are fixed before later layers are updated.Layers matching on all ordered aspects are grouped into order-equivalent classes and processed in lexicographic order.Source: Update order · pp. 8–9

Sampling process

  • The sampler initializes from the null distribution, then uses (pseudo-)Gibbs updates within each order-equivalent class, conditioning later classes on assignments in preceding layers.Fully ordered networks need one update per state node; unordered networks use one class, while partially ordered networks use multiple classes.Source: Sampling process · p. 9

C. Layer-coupled and diagonal interlayer dependencies

  • The layer-coupled restriction reduces the dependency tensor’s dimension while representing temporal, multiplex, and multi-aspect dependencies.Temporal layers typically depend directly on the previous layer, whereas multiplex layers can depend on all other layers; the framework also combines these patterns across aspects.Source: C. Layer-coupled and diagonal… · p. 10, Figure 2 · p. 10, Figure 3 · p. 10

D. Temporal and multiplex partitions

The examples illustrate how the copying probability and dependency pattern shape similarity between induced partitions across layers. In temporal networks, similarity is strongest between adjacent layers and decays with distance; in multiplex networks, it is approximately uniform across layer pairs.

Temporal partitions

Multiplex partitions

  • Multiplex partitions have approximately uniform similarity across layer pairs, and that similarity increases with ˆp.The examples compare color-coded meso-set assignments with NMI values between induced partitions averaged over 10 output partitions.Source: D. Temporal and multiplex partitions · p. 11, Figure 5 · p. 11

Temporal partitions

  • Temporal generation initializes the first layer, then copies each node’s assignment forward with probability p or draws from the next layer’s null distribution, requiring one pass through the layers.The overlap between consecutive layers’ null-distribution supports is necessary for meso-sets to gain new state nodes over time, and null-distribution choice can greatly influence the resulting partitions.Source: D. Temporal and multiplex partitions · pp. 11–12

V. GENERATING NETWORK EDGES

The framework generates multilayer partitions and then allocates edges using planted-partition network models, with options for intralayer and interlayer edges. Numerical examples use these constructions to benchmark community-detection methods across dependency settings.

V. GENERATING NETWORK EDGES

  • The framework can generate networks with intralayer edges, interlayer edges, or both, provided the edge model is a planted-partition model.Its multilayer DCSBM framework extends a single-layer DCSBM to multilayer settings and can incorporate features such as degree correlations.Source: §V · p. 12
  • A simple construction generates a dependent partition first, then independently samples each layer’s edges using a single-layer planted-partition model, so cross-layer connectivity dependence comes from the partitions.Other dependencies, including interlayer degree correlations, edge correlations, and temporal burstiness, can also be incorporated.Source: §V · p. 12

VI. NUMERICAL EXAMPLES

  • The numerical examples benchmark multilayer modularity variants and multilayer InfoMap on temporal, multiplex, and multi-aspect networks with varying dependency structures.The edge benchmarks use a DCSBM mixing parameter µ: at µ = 0 all edges lie within communities, while at µ = 1 edges are distributed independently of communities.Source: §VI · pp. 12–13
  • Results average ⟨NMI⟩ over planted partitions, networks, and algorithm runs; InfoMap on temporal networks at p = 0.99 and p = 1 shows large differences across partitions for some µ values.Each copying-probability and µ pair has 100 benchmark instantiations, and each algorithm runs 10 times per instantiation.Source: §VI · pp. 13–14

A. Multiplex examples

Across multiplex and temporal benchmarks, the results show that multilayer-modularity methods can exploit interlayer dependencies, while outcomes depend on the optimization heuristic and the dependency pattern. Multilayer InfoMap is often less effective, with exceptions under particular settings.

A. Multiplex examples

  • For uniform multiplex dependencies, GenLouvain switches from single-layer-like partitions below ω = 1 to aggregate partitions above ω = 1, without an intermediate regime beating both baselines.GenLouvainRand's additional randomization smooths the transition; reiteration accounts for most of its improvement over GenLouvain.Source: A. Multiplex examples · p. 14, Figure 6 · p. 15

A. Multiplex examples; B. Temporal examples

  • GenLouvainRand beats single-layer and aggregate partitions in most multiplex cases, while both modularity methods improve on single-layer modularity in temporal benchmarks.For temporal networks, peak mean NMI typically occurs around 1 ⪅ ω ⪅ 4; when p < 1, sufficiently large ω can favor persistence absent from the planted partition.Source: A. Multiplex examples · p. 14, B. Temporal examples · p. 16

A. Multiplex examples

  • In multiplex benchmarks, InfoMap finds no meaningful structure for µ > 0.7, whereas GenLouvain methods can do so at µ = 0.9 for sufficiently large ω.For weak structure, InfoMap is worse than its single-layer counterpart unless planted layer partitions are very similar; modularity methods also outperform it when µ and p̂ are both close to 1.Source: A. Multiplex examples · p. 14
  • In nonuniform multiplex networks, GenLouvainRand still exploits dependencies, but its improvement over single-layer modularity is smaller than in uniform cases.At p̂ = 1, aggregate partitions fail to recover the planted partition at sufficiently large ω because planted layer partitions are not identical.Source: A. Multiplex examples · pp. 14–15, Figure 7 · p. 16

B. Temporal examples

  • On temporal benchmarks, multilayer InfoMap is usually similar to or worse than single-layer InfoMap; for uniform dependencies with p = 1, increasing r improves recovery for µ ≤ 0.4.For change-point networks, it correctly recovers change points only at p = 1 and µ = 0 or 0.1.Source: B. Temporal examples · pp. 16–17, Figure 9 · p. 18
  • For temporal benchmarks, the difference between GenLouvain and GenLouvainRand is more pronounced than in multiplex benchmarks, and randomization removes GenLouvain's abrupt change near ω = 1.GenLouvain can nevertheless do better for weak community structure (µ ≥ 0.8), increasingly so as p rises.Source: B. Temporal examples · pp. 16–17
  • Temporal change-point results are mostly similar to uniform-dependency results, except at p = 1.The planted partitions differ across layers even at p = 1 in the change-point setting.Source: B. Temporal examples · p. 17

C. Multi-aspect examples

The multi-aspect example shows how temporal and multiplex coupling affect planted-partition recovery. The conclusions emphasize a flexible framework for specifying dependencies and generating multilayer structures, while noting that the examples cover selected cases.

C. Multi-aspect examples

  • Nonzero temporal or multiplex coupling improves planted-partition recovery over independently maximizing modularity on each layer; stronger temporal weighting shifts good recovery toward larger ωt and smaller ωm.For progressively larger overall dependency strength, mean ⟨NMI⟩ increases slightly while its dependence on ωt and ωm remains similar.Source: Figure 10 · p. 18, C. Multi-aspect examples · p. 19

VII. CONCLUSIONS

  • The framework separates partition generation from edge allocation and explicitly parameterizes interlayer dependencies, spanning single- and multi-aspect networks with uniform or nonuniform dependencies.The framework can be combined with other planted-partition network models and modified to incorporate additional cross-layer dependencies, including degree dependencies or burstiness.Source: §VII · pp. 19–20
  • The examples focus on selected dependency patterns and community structure, although the framework can also construct models for other intralayer mesoscale structures and more realistic multilayer features.The paper describes possible extensions such as temporal memory effects and non-layer-coupled dependencies.Source: §VII · pp. 19–20
  • The authors identify benchmarking, statistical inference, and modeling interdependent data streams as potential applications or extensions of the framework.For fully ordered multilayer networks, the model respects layer causality and can add a new layer without updating previous layers.Source: §VII · p. 20

Appendix A: Example null distributions

Appendix A gives choices for categorical null distributions, including support and label-size controls. Appendix B describes sampling multilayer partitions by respecting the ordering of ordered aspects.

Appendix A: Example null distributions

  • The concentration parameter θ controls the typical meso-set size distribution: θ near 1 favors heterogeneous sizes, large θ favors similar sizes, and sufficiently small θ favors a few large sets and many small ones.The number of labels nset also affects label overlap across layers when interlayer dependencies are absent.Source: Appendix A · pp. 20–21
  • For temporal birth and death, each layer’s support removes active labels with probability rd and adds a Poisson(rb) number of new labels; expected support size approaches rb/rd.The process gives meso-set labels geometric lifetimes, and removed labels’ members can shrink over time according to copying probabilities.Source: Appendix A · p. 21
  • For multiplex partitions, labels can be independently designated active in each layer, with probabilities sampled for active labels and zero probability for inactive ones.Because multiplex layers are unordered, an inactive label need not remain inactive in any subsequent layer.Source: Appendix A · p. 21

Appendix B: Partition sampling process

  • The partition-sampling procedure initializes assignments from layer-specific null distributions, then samples order-equivalent layers together and proceeds sequentially across ordered layer classes.Within each class, assignments in later non-equivalent layers condition on assignments in preceding layers.Source: Appendix B · pp. 21–22

Scan order and compatibility

For potentially incompatible conditional distributions, scan order affects the distribution produced by pseudo-Gibbs sampling. The authors use random layer updates to mitigate fixed-order bias while exploiting within-layer independence.

Scan order and compatibility

  • With potentially incompatible conditionals, different pseudo-Gibbs scan orders correspond to different sampling distributions, unlike compatible Gibbs sampling where scan order affects convergence speed.Under fixed cycling, later-applied conditionals can have outsized influence on the stationary distribution.Source: Scan order and compatibility · p. 22
  • Uniformly random selection of an update distribution mitigates fixed-order influence but adds computational overhead.Source: Scan order and compatibility · p. 22
  • Sampling a layer uniformly at random and updating all its state nodes exploits the independence of conditionals within a layer.The resulting sequence of layer updates defines the sampling Markov chain whose convergence determines algorithm effectiveness.Source: Scan order and compatibility · p. 22

Convergence guarantees

The sampling chain is aperiodic, and it is ergodic over the null-distribution support when every relevant state node has p-hat_i,[?1l>i,α[?1l> < 1. Non-ergodicity can make stationary behavior depend on initialization, so the procedure reinitializes partitions and uses multiple chains.

Convergence guarantees

  • Uniformly sampling layers makes the chain aperiodic because consecutive updates can select the same layer and leave the partition unchanged.A positive probability of remaining in the same state is sufficient for aperiodicity.Source: Convergence guarantees · p. 22
  • When every relevant state node has ˆp_i,α < 1, the chain is ergodic over a subspace that includes the null-distribution support G[α].Any target partition in that support can be reached from any initial partition by updating each state node once.Source: Convergence guarantees · p. 22
  • If some state nodes have ˆp_i,α = 1, the updating process need not be ergodic, and partitions can be absorbing states.When all such probabilities equal 1, partitions assigning one meso-set to each weakly connected component are absorbing.Source: Convergence guarantees · p. 23
  • To address non-unique stationary distributions, the authors reinitialize from the null distribution for each sample; multiple chains are necessary when the process is non-ergodic.Reinitialization defines a unique mixture of possible stationary distributions; independent samples are prioritized over perfect convergence when only a few samples are needed.Source: Convergence guarantees · p. 23

Convergence tests

Convergence is assessed through within-chain autocorrelation and the stability of interlayer dependency patterns. The tests support a conservative choice of nupd = 200, while showing that mixing slows as ˆp increases.

Convergence tests

  • The tests compare mNMI and NMI-matrix distance across update counts and lags, with shaded regions showing one standard deviation.At small lags, Figure 11's substantial noise is inherent to all sampled chains, rather than differences between chains.Source: Figure 11 · p. 23, Convergence tests · p. 24, Figure 12 · p. 24
  • nupd ≈ 50 is sufficient for convergence even when ˆp = 1, and nupd = 200 is a conservative sampling choice.Estimates from the NMI-matrix distance test are consistent with those from the autocorrelation test.Source: Convergence tests · p. 24
  • At stationarity, mixing time increases with ˆp and becomes infinite as ˆp → 1, when the chain reaches an absorbing state.The autocorrelation test uses mNMI across samples separated by different lags.Source: Figure 11 · p. 23, Convergence tests · p. 24
  • For all tested ˆp values, the mean absolute distance between NMI matrices approaches near zero and becomes essentially independent of lag.This supports the assumption that generated partitions have similar interlayer-dependency structure.Source: Convergence tests · p. 24, Figure 12 · p. 24

Appendix C: A generative model for temporal networks

The temporal model generates layer partitions by copying assignments from the previous layer or reallocating them through a null distribution. Uniform dependencies yield automatic convergence after one pass through the ordered layers.

Appendix C: A generative model for temporal networks

  • For fully ordered networks, the temporal model converges automatically after one iteration through the layers.The appendix's model assumes uniform dependencies between contiguous layers and reduces to Algorithm 2.Source: Appendix C · p. 24
  • The model respects time's direction: each layer's meso-set assignments depend on the previous layer and the null distributions.The copying update retains prior assignments with probability p; otherwise, the reallocation update samples from the layer's null distribution.Source: Appendix C · pp. 24–25
  • The copying step can retain, shrink, or eliminate a meso-set, while reallocation can add members or introduce a new label.The interplay of copying and reallocation determines label appearance and disappearance probabilities.Source: Appendix C · p. 25
  • With the same null-distribution probabilities in every layer, expected meso-set counts and sizes remain constant across layers.This describes the case p_α = p for all α.Source: Appendix C · p. 26
  • With nonoverlapping null-distribution supports, existing labels only lose members, new labels appear with probability 1 − p^n, and expected set sizes decrease over time.Overlapping supports are necessary for a meso-set to gain new members in the next layer.Source: Appendix C · p. 26

Appendix D: M-DCSBM sampling procedure

The multilayer degree-corrected SBM uses a partition, block tensor, and state-node parameters to generate edges. The experiments specialize it to undirected intralayer networks, with sampling procedures chosen according to block sparsity.

Appendix D: M-DCSBM sampling procedure

  • The M-DCSBM parameterizes meso-set assignments with S, expected inter-meso-set edge counts with W, and edge allocation to state nodes with σ.The model can generate arbitrary expected layer-specific in-degrees and out-degrees for each state node.Source: Appendix D · p. 26
  • The experiments use undirected networks with intralayer edges only, reducing node parameters to one σ value per state node.Their block tensor has no interlayer contributions in this setting.Source: Appendix D · p. 27
  • For sufficiently sparse blocks, rejection sampling avoids self-edges and multi-edges; dense blocks instead use independent Bernoulli edge sampling.The described network-sampling algorithm scales linearly with the number of edges.Source: Appendix D · pp. 26–27
  • For directed networks, generated expected layer-specific degrees match input values exactly only when μ = 1.Source: Appendix D · p. 28

Appendix E: The Louvain algorithm and its variants

The appendix describes the two-phase Louvain procedure and variants used in the numerical experiments, including distinct move-selection rules and post-processing of assignments.

Appendix E: The Louvain algorithm and its variants

  • Louvain iteratively moves state nodes to maximize modularity, then aggregates the resulting sets and repeats both phases until reaching a local maximum.The first phase stops when no move improves modularity.Source: Appendix E · p. 28
  • GenLouvain selects the modularity-increasing move with the largest gain, whereas GenLouvainRand samples such moves with probability proportional to their gain.GenLouvainRand is a variant of Louvain-Rand, which samples modularity-increasing moves uniformly.Source: Appendix E · p. 28
  • Reiteration reruns GenLouvainRand from its output until the partition stops changing, while post-processing uses the Hungarian algorithm to optimize persistence without changing layer partitions.Persistence is the number of interlayer edges whose endpoints share a community assignment.Source: Appendix E · p. 28

Appendix F: Multilayer NMI experiments

The appendix evaluates multilayer NMI on multiplex and temporal benchmarks, reporting how algorithms recover planted structure under nonuniform dependencies. It cautions that mNMI can conflate cross-layer label correspondence with within-layer recovery.

Appendix F: Multilayer NMI experiments

  • mNMI depends on how communities are corresponded across layers and conflates that labeling with within-layer recovery, so low mNMI can conceal optimal mean NMI.An optimal mean NMI is necessary, but not sufficient, for mNMI to equal 1.Source: Appendix F · p. 29
  • Benchmarks cover multiplex networks with 1000 nodes and 15 layers and temporal networks with 150 nodes and 100 layers, including uniform dependencies and nonuniform cases with abrupt breaks.In the nonuniform temporal benchmark, breaks occur every 25th layer; in the nonuniform multiplex benchmark, dependency blocks have size 5 × 5.Source: Figure 14 · p. 29, Figure 15 · p. 29, Figure 16 · p. 30
  • Post-processing has no major effect on mean NMI, suggesting that misassignments reducing partition persistence do not affect an algorithm’s ability to identify within-layer structure.The appendix omits post-processing in its figures because its effect is expected to be more noticeable for NMI between multilayer partitions.Source: Appendix F · p. 30
  • The reported mNMI values average 10 algorithm runs over 100 benchmark instantiations; curves show means across µ and shaded ranges show minima and maxima across 10 sample partitions.The ranges are for a given p or p-hat.Source: Appendix F · p. 30
  • With nonuniform dependencies, InfoMap detects abrupt breaks better than both GenLouvain variants, especially for multiplex, but correctly recovers planted structure only when µ ≤0.3.The authors attribute imperfect break recovery by multilayer modularity maximization to its incentive for persistence, which the benchmarks exclude across breaks.Source: Appendix F · p. 30

Related papers

Loading 1608.06196v5…