PaperlayerView exact revision on arXiv

Source-linked AI summary

Clustering Network Layers With the Strata Multilayer Stochastic Block Model

Natalie Stanley, Saray Shai, Dane Taylor, Peter J. Mucha

arXiv:1507.01826v2cs.SIphysics.soc-phstat.ML

TL;DR

Multilayer networks offer multiple relational views, but combining layers risks losing information and calls for methods that identify structurally similar layers. The paper introduces sMLSBM to jointly cluster layers and nodes; synthetic comparisons and Human Microbiome Project analysis demonstrate its use.

Abstract

from arXiv · show

Multilayer networks are a useful data structure for simultaneously capturing multiple types of relationships between a set of nodes. In such networks, each relational definition gives rise to a layer. While each layer provides its own set of information, community structure across layers can be collectively utilized to discover and quantify underlying relational patterns between nodes. To concisely extract information from a multilayer network, we propose to identify and combine sets of layers with meaningful similarities in community structure. In this paper, we describe the "strata multilayer stochastic block model'' (sMLSBM), a probabilistic model for multilayer community structure. The central extension of the model is that there exist groups of layers, called "strata'', which are defined such that all layers in a given stratum have community structure described by a common stochastic block model (SBM). That is, layers in a stratum exhibit similar node-to-community assignments and SBM probability parameters. Fitting the sMLSBM to a multilayer network provides a joint clustering that yields node-to-community and layer-to-stratum assignments, which cooperatively aid one another during inference. We describe an algorithm for separating layers into their appropriate strata and an inference technique for estimating the SBM parameters for each stratum. We demonstrate our method using synthetic networks and a multilayer network inferred from data collected in the Human Microbiome Project.

I. INTRODUCTION

Multilayer networks combine distinct relational definitions across layers, motivating methods that use information across layers while preserving structural patterns. This section frames sMLSBM as a generative approach to grouping layers by community structure and jointly clustering nodes.

I. INTRODUCTION

  • Multilayer networks represent different relational definitions as layers, allowing information about connections among the same entities to be analyzed collectively.Source: §I · p. 1
  • The central question is whether layers contain redundant information and can be compressed without losing useful structure; aggregation can also corroborate patterns and improve community detection.Source: §I · p. 1
  • Earlier layer clustering used an information-theoretic distance and a quality function for aggregation, but did not provide a generative model for clusters of redundant layers.Source: §I · p. 1

A. Network Comparison Based on Community Structure

  • Network-layer clustering is related to clustering network ensembles, while community analysis often uses assortative communities or generative SBMs that describe within- and between-community edge probabilities.Source: A. Network Comparison Based on… · pp. 1–2

B. Related Work on Multilayer SBMs

Prior multilayer SBMs generally model shared community patterns across layers, with approaches differing in parameterization and treatment of aggregation. The paper positions sMLSBM against work that does not group layers under multiple distinct SBMs.

B. Related Work on Multilayer SBMs

C. Contributions

The paper introduces sMLSBM to group layers into strata while clustering nodes into communities under shared stratum-specific SBMs. Its iterative inference couples both assignment tasks, and the paper evaluates the method on synthetic and Human Microbiome Project networks.

C. Contributions

  • sMLSBM groups layers into strata assumed to share an underlying generative SBM, while jointly assigning layers to strata and nodes to communities.Source: C. Contributions · p. 3
  • An iterative algorithm combines the two assignments, so improved community detection can improve layer clustering and vice versa.Source: C. Contributions · p. 3
  • The paper defines the model and fitting algorithm, tests synthetic networks, and evaluates correlation networks constructed from Human Microbiome Project data.Source: C. Contributions · p. 3

A. Network Definition

A multiplex network is represented as a set of network layers, each with an adjacency matrix representation.

A. Network Definition

  • A multiplex network comprises indexed network layers, each defined by its nodes and edges and represented by an adjacency matrix.Source: A. Network Definition · p. 3

B. Model Definition

The sMLSBM groups layers into strata whose community structure is represented by shared stochastic block model parameters and node assignments. Its fit jointly identifies layer-to-stratum and node-to-community assignments and estimates the parameters for each stratum.

B. Model Definition

  • Layers in a stratum share SBM parameters and similar node-to-community assignments, while these parameters can differ across strata.The model represents each stratum with parameters πs and Zs.Source: Figure 1 · p. 3, B. Model Definition · p. 3
  • Fitting the model estimates each layer’s stratum and the SBM parameters and community assignments associated with each stratum.The stratum parameters represent a consensus for its associated layers.Source: B. Model Definition · pp. 3–4
  • For each stratum, the model uses πs and Zs; these define an adjacency probability matrix θs whose entries give edge probabilities between nodes.The number of communities Ks may vary across strata.Source: B. Model Definition · p. 3
  • The layer-to-stratum assignments encode a partition: each layer is assigned to one stratum, and the strata together cover all layers.Source: B. Model Definition · pp. 3–4

C. Inference for sMLSBM

The inference procedure first clusters layers to initialize strata, then iteratively refines layer-to-stratum and node-to-community assignments alongside stratum-level SBM parameters. It uses variational inference for the stratum likelihood and handles disagreement between layer representations by creating additional strata.

C. Inference for sMLSBM

  • A two-phase procedure initializes strata by clustering layers, then jointly updates layer-to-stratum and node-to-community assignments and stratum parameters.This greedy initialization reduces the search space because only node assignments must then be statistically inferred.Source: C. Inference for sMLSBM · p. 4, Figure 2 · p. 4
  • Phase I fits an SBM to each layer separately, constructs adjacency probability matrices, and clusters those matrices to initialize strata.The number of strata can be specified in advance or approximated using a measure such as the gap statistic.Source: C. Inference for sMLSBM · p. 4
  • Phase II estimates a consensus SBM for each stratum by maximizing the likelihood across its layers, using a variational approximation because the conditional distribution is intractable.The procedure follows an expectation-maximization framework for maximum-likelihood estimation with incomplete data.Source: C. Inference for sMLSBM · pp. 4–5
  • Within each stratum, the algorithm alternates updates to τs and πs until convergence, yielding consensus community assignments and SBM parameters.Source: C. Inference for sMLSBM · p. 5
  • Phase II forms two layer-specific adjacency-probability representations from stratum-consensus and layer-specific estimates, then clusters both representations to reassess strata.If the representations assign a layer differently, their disagreement indicates assignment uncertainty; the algorithm creates an additional stratum for each resulting membership combination.Source: C. Inference for sMLSBM · pp. 5–6
  • Layers cannot have mixed stratum membership; alternative ways to handle disagreement between their representations are left for future work.The described approach creates additional strata for combinations of membership that arise.Source: C. Inference for sMLSBM · p. 6
  • Phase II repeats until layer-to-stratum assignments stop changing; although new strata could arise at each iteration, this did not occur in the reported synthetic or real-data experiments.The authors note that bounding the number of iterations may help if strata continue to arise.Source: C. Inference for sMLSBM · p. 6

A. Comparison of sMLSBM to other SBM Approaches

In a synthetic network with three strata, the sMLSBM was compared with a single SBM fitted across all layers and separate SBMs fitted to each layer. In this example, the authors report that sMLSBM outperforms both alternatives.

A. Comparison of sMLSBM to other SBM Approaches

  • The experiment generated 30 layers in three strata, with 10 layers per stratum, 128 nodes per layer, four communities, and expected mean degree 20.The extent of block structure decreased from stratum 1 to stratum 3, and node-to-community assignments differed between strata.Source: A. Comparison of sMLSBM to other SBM… · p. 6
  • In this synthetic example, sMLSBM outperforms both a single SBM fitted across all layers and separate single-layer SBMs.The comparison evaluates SBM parameter estimation and node-to-community assignment accuracy.Source: A. Comparison of sMLSBM to other SBM… · p. 6
  • The authors compared models using mean ℓ2 error in estimated SBM parameters and mean normalized mutual information for community assignments across layers.The figure describes parameter error in panel B and community-assignment NMI in panel C.Source: A. Comparison of sMLSBM to other SBM… · p. 6

B. Synthetic Experiment with Two Strata

In synthetic networks, sMLSBM recovered layer-to-stratum assignments better than k-means, and increasing the number of layers generally improved strata identification and community detection.

B. Synthetic Experiment with Two Strata

  • The simulations used L = 10 or 100 layers, two equally sized strata, four communities per stratum, and 128 nodes per layer.Stratum 1 was fixed at N(p1 in − p1 out) = 10, while the second stratum's detectability was varied; the plotted means were over 50 networks with standard-error bars.Source: B. Synthetic Experiment with Two Strata · pp. 6–7
  • At N(p2 in − p2 out) = 10, the two strata are indistinguishable under the experiment's parameterization.The experiment identifies this threshold with equality of the strata's within- and between-community probabilities.Source: B. Synthetic Experiment with Two Strata · p. 7
  • sMLSBM consistently achieved higher NMI for layer-to-strata assignments than k-means, with both methods performing moderately well at L = 100 before the strata became indistinguishable.The experiment also tracked Phase II iterations to convergence; their peaks corresponded to sudden jumps in strata NMI.Source: B. Synthetic Experiment with Two Strata · p. 7
  • As strata NMI rose, node-to-community NMI stabilized; when strata assignments were poor, incorrect layer mixing weakened community detection.The authors report that increasing L generally improved both community detection and strata identification.Source: B. Synthetic Experiment with Two Strata · p. 7

IV. CORRELATION NETWORKS FROM THE HUMAN MICROBIOME PROJECT

Applied to SparCC microbiome networks from 18 body sites, sMLSBM identified six strata of sites with similar microbiomes. The inferred groups were biologically meaningful, while hierarchical clustering depended strongly on where its tree was cut.

IV. CORRELATION NETWORKS FROM THE HUMAN MICROBIOME PROJECT

  • The analysis thresholded SparCC edge weights at 0.2 and retained OTUs present in at least two layers, yielding 213 nodes across 18 body-site networks.The input networks were inferred using SparCC from Human Microbiome Project data.Source: §IV · pp. 7–8
  • The fitted sMLSBM identified six strata, grouping body sites with similar microbiomes and separating them from sites in other strata.The stratum with six layers appeared to be a miscellaneous cluster.Source: §IV · p. 8
  • Hierarchical-clustering partitions depended strongly on the tree cut, and it was difficult to find a cut as meaningful as the sMLSBM grouping.Saliva, hard palate, and tongue dorsum were described as an intuitive group with similar microbial interaction networks.Source: §IV · p. 8
  • In four of the six strata, representative network layers showed similar block structure within each stratum.Each figure row shows a sample network generated with the stratum's learned SBM parameters alongside two representative layers; some strata have more than two members.Source: §IV · p. 8

V. CONCLUSION AND FUTURE WORK

The sMLSBM jointly partitions layers into strata and nodes into communities, using shared structure to improve inference. The conclusion highlights its ability to reveal layer similarities while noting restrictions on network types and signed edges.

V. CONCLUSION AND FUTURE WORK

  • The sMLSBM jointly partitions layers into strata and nodes into communities, assuming layers in a stratum share an underlying SBM.Inference alternates between layer-to-stratum assignments and updates to each stratum’s model parameters.Source: §V · p. 8
  • Fig. 6 displays networks from four of the six identified strata; each row pairs a generated sample with two SparCC networks from that stratum, showing strong within-row similarity.Source: Figure 6 · p. 9
  • Inaccuracies can arise from fitting one SBM to a multiplex network or studying its layers in isolation, whereas sMLSBM reveals similarities in community structure.More accurate node-to-community assignments and SBM probability estimates improve one another.Source: §V · p. 9
  • The implemented sMLSBM is limited to unweighted, undirected networks; degree correction, overlapping communities, and mixed membership are proposed extensions.Source: §V · p. 9
  • In the microbiome example, negative edges were thresholded away despite the importance of antagonistic relationships, motivating a signed sMLSBM extension.Source: §V · p. 9
  • The authors present sMLSBM as a tool for finding signal in inherently noisy and complex multilayer network data.Source: §V · p. 9

Related papers

Loading 1507.01826v2…