PaperlayerView exact revision on arXiv

Source-linked AI summary

Inferring the mesoscale structure of layered, edge-valued and time-varying networks

Tiago P. Peixoto

arXiv:1504.02381v3physics.soc-phphysics.data-an

TL;DR

Mesoscale organization may be intertwined with layers, edge values, or time, but it remains difficult to determine when those dimensions matter and how finely to model them. The paper uses Bayesian model selection over generative network models to balance fit against complexity. It identifies uninformative layers as a threat to structure detection and proposes comparisons that avoid that pitfall.

  • Problem

    Mesoscale structure can be intertwined with layered or temporal organization, raising the question of whether those dimensions matter and at what granularity.

    Source: §I · pp. 1–2

  • Method

    The framework uses Bayesian model selection among generative SBM variants, balancing model complexity and fit using statistical evidence.

    Source: §I · p. 2, §VII · p. 13

  • Results

    Uncorrelated layers can obstruct mesoscale detection, but comparing against an uncorrelated-layer null or a coarse-grained model avoids this problem.

    Source: §VII · p. 13

  • Takeaways & Limitations

    The framework provides a principled way to infer parsimonious layered, edge-valued, and temporal network models and their appropriate granularity.

    Source: §VII · p. 13

Abstract

from arXiv · show

Many network systems are composed of interdependent but distinct types of interactions, which cannot be fully understood in isolation. These different types of interactions are often represented as layers, attributes on the edges or as a time-dependence of the network structure. Although they are crucial for a more comprehensive scientific understanding, these representations offer substantial challenges. Namely, it is an open problem how to precisely characterize the large or mesoscale structure of network systems in relation to these additional aspects. Furthermore, the direct incorporation of these features invariably increases the effective dimension of the network description, and hence aggravates the problem of overfitting, i.e. the use of overly-complex characterizations that mistake purely random fluctuations for actual structure. In this work, we propose a robust and principled method to tackle these problems, by constructing generative models of modular network structure, incorporating layered, attributed and time-varying properties, as well as a nonparametric Bayesian methodology to infer the parameters from data and select the most appropriate model according to statistical evidence. We show that the method is capable of revealing hidden structure in layered, edge-valued and time-varying networks, and that the most appropriate level of granularity with respect to the additional dimensions can be reliably identified. We illustrate our approach on a variety of empirical systems, including a social network of physicians, the voting correlations of deputies in the Brazilian national congress, the global airport network, and a proximity network of high-school students.

I. INTRODUCTION

The paper asks when layers and temporal structure reveal mesoscale organization, and how to distinguish that structure from stochastic variation. It introduces layered SBM variants and Bayesian model selection to choose model classes and granularity using statistical evidence.

I. INTRODUCTION

  • Layered or temporal organization can intertwine with mesoscale structure, while incorporating uninformative layers can hinder its detection.The paper frames the task as deciding whether these dimensions matter and, if so, at what granularity.Source: §I · p. 1
  • A nonparametric Bayesian framework selects model classes and their order by statistical evidence and parsimony, without ad hoc parameters.The selected order can include the number of groups, layer bins, and hierarchical structure.Source: §I · p. 2

II. GENERATIVE MODELS OF LAYERED NETWORKS

  • Two layered-network generation schemes either assign edge layers conditional on a collapsed graph or generate layers independently.These are termed “edge covariates” and “independent layers,” respectively.Source: §II · p. 2

A. SBM with edge covariates

  • With edge covariates, the model generates a collapsed SBM first and distributes edge-layer membership conditional on group-pair edge counts.The collapsed SBM can be replaced by other flavors, including degree correction; this version constrains only collapsed degrees, not degree variation across layers.Source: A. SBM with edge covariates · pp. 2–3

B. SBM with independent layers

The independent-layers SBM generates each layer as its own SBM while retaining shared group memberships, with options for layer-specific node participation and degree correction. These options allow layer-specific degrees—and hence effective group mixtures—to vary across layers.

B. SBM with independent layers

  • Each layer is generated as an SBM, with layer-specific degree sequences available for degree correction.The model’s likelihood is built from the traditional SBM likelihood for each layer’s subgraph.Source: B. SBM with independent layers · p. 3
  • A layer-membership matrix can restrict which nodes receive edges in each layer, while overall group memberships remain shared.In the degree-corrected version, zero layer-specific degree means a node receives no edges in that layer, replacing explicit layer-membership parameters.Source: B. SBM with independent layers · p. 3
  • Layer-specific labeled degrees act as changing group weights, allowing memberships to shift across layers despite constant overall mixtures.The passage identifies this flexibility as useful for temporal networks, where group membership may change over time.Source: B. SBM with independent layers · p. 3

C. Equivalence between models

The two model families can coincide under restricted conditions, but independent layers are more expressive when node participation or degree patterns vary by layer. That extra flexibility has a complexity cost, motivating evidence-based model choice.

C. Equivalence between models

  • With non-degree-corrected models and all nodes in all layers, edge covariates and independent layers are asymptotically equivalent when layer edge counts are sufficiently large.If nodes belong only to subsets of layers, only independent layers accounts for that heterogeneous membership.Source: C. Equivalence between models · p. 4
  • For degree-corrected models, independent layers allows layer-specific degree variation that edge covariates cannot represent, while it can also reproduce edge-covariate networks.Source: C. Equivalence between models · p. 4
  • Independent layers requires more parameters, so always choosing the more flexible model risks overfitting.The passage points to model comparison in the next section as the way to choose between them.Source: C. Equivalence between models · p. 4

III. SELECTING THE MOST APPROPRIATE MODEL

The procedure selects models by balancing fit against complexity through Bayesian evidence and minimum description length. Nonparametric priors specify model parameters and allow key structural choices to be inferred without ad hoc settings.

III. SELECTING THE MOST APPROPRIATE MODEL

  • The preferred model maximizes posterior probability, equivalently minimizing description length and balancing model complexity against fit.The description length combines data entropy with the description length of the parameter ensemble.Source: §III · p. 4
  • Nonparametric priors infer the partition, overlap, number of groups, and hierarchy without ad hoc parameter choices.The method selects among model classes and their orders, including the number of groups and layer bins.Source: §III · p. 4

A. Choice of priors

  • Nested priors and hyperpriors place the uninformative prior at the top level to reduce sensitivity to prior choices.Layer-specific degree sequences are assumed independent, a simplification motivated by the limited evidence available as layer count grows.Source: A. Choice of priors · pp. 4–5
  • Priors generate partitions, layer memberships, degree sequences, and edge counts as components of each model’s description length.The edge-count prior uses a nested sequence of stochastic block models to represent hierarchical structure.Source: A. Choice of priors · pp. 4–5

B. Confidence levels

Posterior odds ratios provide a nonparametric way to express confidence when comparing model hypotheses. Their size indicates the strength of evidence against the less-preferred model.

B. Confidence levels

  • The posterior odds ratio compares two hypotheses using their parameter posteriors and prior probabilities, with description-length difference determining the evidence ratio.The paper assumes equal prior probabilities and places the preferred hypothesis in the denominator.Source: B. Confidence levels · pp. 5–6
  • An odds ratio below 1 rejects the numerator hypothesis in favor of the denominator, with confidence increasing as the ratio falls.A ratio of 1/100 is treated as decisive evidence, while ratios from 1/3 to 1 indicate only a negligible difference.Source: B. Confidence levels · p. 6
  • When neither model is given prior preference, the posterior odds ratio is the Bayes factor.Source: B. Confidence levels · p. 6

C. Inference algorithm

Because exhaustive search over hierarchical partitions is impractical, inference uses approximate multilevel MCMC methods. Sparse data structures keep typical greedy running times at O(N ln^2 N), independent of group and layer counts.

C. Inference algorithm

  • Exhaustive evaluation of every hierarchical partition is impractical beyond networks with a few nodes and edges, so the method uses approximate optimization.Source: C. Inference algorithm · p. 6
  • Inference uses multilevel MCMC with hierarchical and overlapping-group extensions, whose agglomerative moves can overcome metastable states.Source: C. Inference algorithm · p. 6
  • Sparse data structures keep typical greedy running times at O(N ln^2 N), independent of group and layer counts; belief propagation and spectral clustering are alternatives if adapted to the likelihoods.Source: C. Inference algorithm · p. 6

IV. WHEN ARE LAYERS INFORMATIVE?

Layer information can reveal structure hidden by collapsing a network, but uninformative or overly numerous layers can reduce inference quality. The examples show both evidence for informative layers and cases where the collapsed network suffices.

IV. WHEN ARE LAYERS INFORMATIVE?

  • Layers are informative when they produce a more detailed description than the collapsed network, as the example’s random collapsed graph conceals four groups.Source: §IV · p. 6
  • When layers are unrelated to group divisions, increasing their number makes each layer sparser and worsens inference; independent-layer detectability tends toward c*=1 as C approaches E.The edge-covariate model performs relatively better, but also degrades noticeably as layer count increases.Source: §IV · pp. 6–7, Figure 3 · p. 7
  • For the physicians network, the edge-covariate model is rejected against the collapsed fit (Λ ≈ 10^-51), providing no noticeable evidence that acquaintance types track large-scale structure.The authors conclude that overall acquaintances, rather than their surveyed types, are the important descriptors in this network.Source: Figure 4 · p. 7, §IV · p. 8
  • The coalition shift between Brazil’s 1999–2002 and 2003–2006 terms disappears in the collapsed network, which is strongly rejected against the layered model (Λ ≈ 10^-111).The layered model reveals the changing government and opposition groupings.Source: §IV · p. 8, Figure 5 · p. 9
  • Layers can be grouped into bins so their granularity is selected rather than assumed; merging bins by description-length reduction is one proposed approach.A single bin recovers the null model with random layer assignments.Source: §IV · pp. 7–9

A. Layers as evidence for overlaps

Layer information can alter how overlapping structure in a collapsed graph is interpreted: edges may encode latent layers, and including their layer assignments can favor a layered model. The comparison still depends on what information is observed and on the description lengths of the candidate models.

A. Layers as evidence for overlaps

  • Collapsed overlapping structure can be interpreted as latent layers, with each connected group pair corresponding to a layer.Prior knowledge of the layer division can change the interpretation when a nonoverlapping model otherwise fits the collapsed graph better.Source: A. Layers as evidence for overlaps · p. 9
  • The example generates C layers with random edge placement and uses μ to control their overlap, from asymptotically nonoverlapping layers to identical mixture sizes.After collapsing, the same topology can be represented by an overlapping SBM with C groups or a nonoverlapping SBM with 2C − 1 groups.Source: A. Layers as evidence for overlaps · p. 9
  • With layer assignments included, the B = 1 model with independent layers is preferred throughout the example’s parameter range.The added information supports this layered variant but does not decide between the two collapsed models.Source: A. Layers as evidence for overlaps · p. 10
  • Ref. found overlapping SBM variants seldom best fit the empirical networks it studied without layer information; this example shows that assessment may change when an edge division is assumed a priori.The authors argue that fair model assessment should use available layer or edge-covariate information.Source: A. Layers as evidence for overlaps · p. 10

V. EDGES WITH REAL-VALUED CORRELATES

The method discretizes real-valued edge correlates into layers and infers an appropriate binning from the data. In the airport network, distance-based layers reveal regional and distance-related organization, including hubs spanning multiple layers.

V. EDGES WITH REAL-VALUED CORRELATES

  • Real-valued edge correlates are discretized into layers, each assigned a value sampled from a probability density; distinct values for every edge correspond to C = E layers.The layers can then be grouped into bins, each associated with parameters of a layered SBM.Source: §V · p. 10
  • The correlate density contributes a bin-independent multiplicative factor to the likelihood, so its form need not be specified for maximum-likelihood or posterior estimation.The passage contrasts this with Ref., which requires specifying the correlate distribution, while not requiring binning.Source: §V · p. 10
  • Posterior maximization determines both the number of correlate bins and their boundary positions from the data.The airport example applies this procedure to geodesic distances.Source: §V · pp. 10–11
  • The airport fit selects 34 groups and five distance bins, with groups forming fairly contiguous regions and layers organizing flights from local to increasingly interregional distances.High-degree airports tend to belong to multiple layers, serving both short- and long-distance routes.Source: §V · p. 11, Figure 7 · p. 11

VI. TIME-VARYING NETWORKS

The paper treats temporal networks as networks with time-valued edge correlates and compares layered model variants to capture temporal patterns. Its examples identify periods with distinct network structure, including changing deputy alignments and activity shifts in a school proximity network.

VI. TIME-VARYING NETWORKS

  • Temporal networks can be represented as real-valued edge correlates, with edge time as the correlate and the real-valued covariate approach applied to them.Other temporal formulations, such as edge creation and deletion times, can be handled with multidimensional bins.Source: §VI · p. 11
  • Time bins assume edges are placed randomly between groups within each bin; model variants differ in whether node activity is shared, separately regulated, or degree-corrected by layer.Standard group memberships remain stable over time, whereas an overlapping SBM allows memberships to change across time.Source: §VI · p. 11
  • A time-bin boundary can be interpreted as a change point when large-scale network structure changes measurably and significantly across bins.This interpretation follows from assuming that within-bin edge placement is independent of the edges’ relative times.Source: §VI · p. 12
  • The high-school proximity network is divided into 10 periods and 33 groups; the hierarchy accords with three classes, while periods alternate between high activity and relative quiet.The authors suggest these periods may correspond to breaks and class periods, but note that the dataset lacks this contextual information.Source: §VI · p. 12
  • In the Brazilian congress network, the best fit is an overlapping DCSBM with independent layers and 12 groups, with deputy alignment changes across years largely confined to government or opposition.The inferred flows appear mostly unrelated to party changes and instead reflect finer-grained alignment patterns.Source: §VI · pp. 12–13

VII. CONCLUSION

The framework uses Bayesian model selection to infer mesoscale structure in layered, edge-valued, and time-varying networks while balancing model complexity and fit. It addresses the risk that uncorrelated layers obscure structure and can identify useful scales and change points.

VII. CONCLUSION

  • The framework infers mesoscale structure across layered, edge-valued, and time-varying networks, balancing model complexity and fit through Bayesian model selection.It incorporates hierarchical structure, degree correction, and overlapping groups.Source: §VII · p. 13
  • Uncorrelated layers can obstruct mesoscale structure identification; comparison with an uncorrelated-layer null model or a coarse-grained model can avoid this problem.The issue matters especially with many layers, including arbitrary bins of edge covariates or time.Source: §VII · p. 13
  • The framework extends to real-valued edge attributes and temporal networks, identifying scales where mesoscale structure changes little.Those scales support coarse-graining into discrete layers and detection of network-structure change points.Source: §VII · p. 13
  • The approach offers a parsimonious, evidence-based analysis without ad hoc parameters, with potential uses including missing valued-edge prediction and identifying relevant time scales.The paper also relates relevant time scales to dynamical processes on temporal networks.Source: §VII · pp. 13–14

Appendix A: Multigraphs

The appendices adapt the likelihoods and model-selection procedure to multigraphs and directed graphs, and specify a Bayesian process for selecting overlapping partitions and degree sequences.

Appendix A: Multigraphs

  • For multigraphs, likelihoods account for indistinguishable parallel edges within a layer; the resulting parameter-independent factor does not change the most likely partition but matters when comparing models with different layer counts.Independent-layer likelihoods use the appropriate multigraph likelihood in each layer, and the null and binned-layer models also require corresponding modifications.Source: Appendix A · p. 14

Appendix B: Directed graphs

  • Directed-graph versions modify the collapsed likelihoods and priors, while edge-covariate, independent-layer, null, and binned-layer likelihoods receive directed-graph adjustments.The collapsed likelihoods and priors refer to Refs..Source: Appendix B · p. 14

Appendix C: Model selection for overlapping groups

  • For overlapping groups, a hierarchical Bayesian process assigns a description length to the partition, with maximum mixture size D; setting D = 1 recovers the non-overlapping case.A similar Bayesian process generates the collapsed overlapping degree sequence.Source: Appendix C · pp. 14–15
Loading 1504.02381v3…