PaperlayerView exact revision on arXiv

Source-linked AI summary

Structure and inference in annotated networks

M. E. J. Newman, Aaron Clauset

arXiv:1507.04001v1cs.SIphysics.data-anphysics.soc-phstat.ML

TL;DR

Community detection often has access to node metadata but lacks a principled way to know whether those annotations align with the desired communities. The paper develops a Bayesian, metadata-aware stochastic block model that learns whether to use the annotations, improving detection and enabling metadata-only membership prediction.

  • Problem

    The paper asks how to incorporate node metadata into community detection without assuming that metadata correlate with the communities of interest.

  • Method

    The method fits a degree-corrected stochastic block model whose community priors depend on metadata, learning the metadata–community relationship through Bayesian inference.

  • Results

    98% versus 6%: with metadata, the algorithm found the correct division in synthetic tests almost every time, compared with network structure alone.

  • Takeaways & Limitations

    The learned relationship can improve community detection, select among competing divisions, quantify metadata–community agreement, and predict membership for nodes lacking network data.

Abstract

from arXiv · show

For many networks of scientific interest we know both the connections of the network and information about the network nodes, such as the age or gender of individuals in a social network, geographic location of nodes in the Internet, or cellular function of nodes in a gene regulatory network. Here we demonstrate how this "metadata" can be used to improve our analysis and understanding of network structure. We focus in particular on the problem of community detection in networks and develop a mathematically principled approach that combines a network and its metadata to detect communities more accurately than can be done with either alone. Crucially, the method does not assume that the metadata are correlated with the communities we are trying to find. Instead the method learns whether a correlation exists and correctly uses or ignores the metadata depending on whether they contain useful information. The learned correlations are also of interest in their own right, allowing us to make predictions about the community membership of nodes whose network connections are unknown. We demonstrate our method on synthetic networks with known structure and on real-world networks, large and small, drawn from social, biological, and technological domains.

I. INTRODUCTION

The paper extends community detection by incorporating node metadata into network analysis without assuming metadata correlate with the communities. The method learns whether metadata are informative, can select among competing divisions, and can predict community membership from metadata alone.

  • I. INTRODUCTION: The paper addresses the common separation between network topology and node metadata by incorporating annotations such as age, gender, location, or biological function.The approach is based on statistical inference and focuses specifically on community detection.
  • I. INTRODUCTION: Community detection searches for a division of network nodes into groups, typically with denser within-group than between-group connections.The task is also called node clustering or classification.
  • I. INTRODUCTION: The method learns and quantifies whether metadata correlate with communities, using informative signals while automatically ignoring uninformative metadata.It can still exploit imperfect or noisy correlations rather than requiring a priori alignment.
  • I. INTRODUCTION: Metadata can steer analysis toward a desired division when a network has multiple meaningful community partitions.The method can also decline to follow metadata that do not correlate with a good network division.
  • I. INTRODUCTION: Learned metadata–community correlations quantify agreement and enable predictions of community membership for nodes whose network connections are unknown.For example, learned age associations can predict social group membership from age alone.
  • I. INTRODUCTION: The paper evaluates the approach on benchmark and real-world networks and reports higher accuracy than methods using network structure alone.The reported applications span social, biological, and technological domains.

II. METHODS

The method uses Bayesian inference with a metadata-dependent, degree-corrected stochastic block model. It fits the model to networks and annotations to infer communities and metadata–community correlations, using specialized treatments for discrete and ordered metadata.

  • II. METHODS: Bayesian inference fits a generative model containing community structure and metadata correlations to an observed network plus metadata.The fitted parameters describe the network structure and the metadata–community relationship.
  • II. METHODS: The model is a modified stochastic block model with degree correction and metadata-dependent community priors.Degree correction accommodates heterogeneous observed degree sequences, while the learned prior links community membership to metadata.
  • II. METHODS: For discrete metadata, each node receives a community assignment with probability γ_sx determined by its metadata value, after which edges are generated independently according to community parameters.Missing metadata are represented as an additional metadata value.
  • II. METHODS: The edge model uses θ_st for community pairs and a d_ud_v factor so it can fit arbitrary degree sequences.The parameters satisfy θ_st = θ_ts for the undirected network.
  • II. METHODS: Community detection fits the model by maximum likelihood using the network adjacency matrix and metadata.The likelihood sums over possible community assignments and depends on network parameters Θ and metadata parameters Γ.
  • II. METHODS: The EM algorithm estimates Θ and Γ, with posterior quantities representing individual and joint community-assignment probabilities.Belief propagation is used instead of direct evaluation of the exponentially large assignment sum.
  • II. METHODS: For ordered or continuous metadata, the prior P(s | x) is represented with basis functions and coefficients γ_sj.The implementation uses finite-degree polynomials, specifically Bernstein polynomials, with iterative coefficient updates.

III. RESULTS

The paper applies the method to computer-generated benchmarks and a variety of real-world networks. These evaluations test recovery of known structure and performance across practical network data sets.

  • III. RESULTS: The evaluation covers computer-generated benchmarks designed to test detection of known community structure.The benchmarks are part of a broader set of example-network applications.
  • III. RESULTS: The evaluation also includes a variety of real-world networks.The passage identifies real-world applications but does not specify their domains or quantitative outcomes.
  • III. RESULTS: The experiments assess the method across both controlled and practical network settings.This combines benchmark tests of known structure with applications to observed networks.

A. Synthetic networks

Synthetic tests show that metadata can improve community detection when it correlates with planted communities, including below the network-only detectability threshold. The method also uses weak metadata correlations to select a desired division among competing alternatives.

  • Metadata generated to match planted community assignments at varying fractions improved detection as their correlation with communities increased.At exactly 50% agreement, metadata were uncorrelated and provided no help; higher agreement levels produced better performance.
  • For strong network structure, the algorithm classified essentially all nodes correctly, while weaker structure reduced accuracy across metadata conditions.Performance remained higher whenever metadata were useful than in the uncorrelated 50% condition, and appeared to increase monotonically with metadata correlation.
  • Because EM is optimal without metadata, better performance with metadata exceeds what any structure-only algorithm can achieve on average.This comparison applies to the community-detection setting without metadata described in the passage.
  • Below the network-only detectability threshold, accuracy remained roughly equal to the fraction of metadata matching the communities and sometimes exceeded that baseline.This suggests metadata can shift the threshold downward or possibly eliminate it, although the passage presents this as an interpretation of the figure.
  • The method combines network structure and metadata, using only the information that contributes to community detection.It is described as correctly ignoring either source when that source contains no community information.
  • With 65% metadata agreement, the algorithm selected the desired two-way division in 98% of synthetic tests, compared with 6% without metadata.The test used four equally sized underlying communities and evaluated whether more than 85% of nodes were correctly classified.

B. Real-world networks

Across social, biological, and technological networks, metadata helped the method select divisions aligned with relevant node properties while being ignored when no useful network correlation existed. The real-world examples show both strong metadata–community agreement and selection among competing divisions.

  • School friendships: The 795-student friendship network contains distinct divisions by school, ethnicity, and other attributes, allowing metadata to steer community detection toward a chosen division.The network combines middle and high schools, with previously documented divisions corresponding roughly to schools and ethnicity-based divisions also present.
  • School friendships: School grade metadata produced a division separating grades 7–8 from grades 9–12, corresponding to middle school and high school.The algorithm was asked to find two communities and readily recovered the school-level split.
  • School friendships: Ethnicity metadata produced two groups consisting principally of Black students and White students, with remaining students distributed roughly evenly.The metadata had four main values—White, Black, Hispanic, and Other—plus a small number of missing entries.
  • School friendships: Gender metadata was ignored because it did not correspond to a good network division; the algorithm instead found a hybrid of grade and ethnicity structure.The resulting groups included White high-school students in one group and everyone else in the other, and metadata were used only when they increased likelihood.
  • Marine food web: In the 488-species Weddell Sea food web, log body mass yielded three groups closely matching ecosystem roles, from primary producers and herbivores to omnivores and carnivores.Low-mass organisms were concentrated in the first group, intermediate-mass organisms in the second, and high-mass organisms in the third.
  • Internet graph: For the 46 676-node Internet graph, blind community detection produced NMI values from 0.626 to 0.398, illustrating that competing divisions can differ in alignment with country metadata.The metadata-guided algorithm is intended to select divisions correlated with the variable of interest rather than force every division to align with it.

IV. CONCLUSIONS

The paper presents a metadata-aware technique for network community detection that learns whether annotations correlate with network structure. Across controlled and real-world data, it improves community-detection results and supports flexible selection among competing divisions.

  • Conclusions: The technique incorporates node metadata directly into network analysis, focusing on community detection while allowing broader applications in principle.The method is demonstrated on social, biological, and technological data sets.
  • Conclusions: The method infers metadata–network correlation and automatically uses or ignores metadata accordingly, rather than assuming that a correlation exists.This supports selecting among competing community divisions when only some align with the variable of interest.
  • Future work: Possible extensions include more complex metadata, other network structures, and predictions of missing links or metadata, which the paper leaves for future work.Examples include mixed discrete and continuous variables, spatial coordinates, hierarchy, rankings, and latent-space structure.

Appendix A: EM algorithm

The appendix derives the expectation–maximization algorithm used to fit the paper’s model to empirical network data.

  • EM algorithm: The appendix presents the derivation of the expectation–maximization algorithm used to fit the model.Its stated application is fitting the model to empirical network data.
  • EM algorithm: The EM algorithm is used for model fitting on empirical network data.
  • EM algorithm: The appendix focuses on derivation rather than describing a separate empirical application.

1. Unordered data

For unordered metadata, the method incorporates discrete node attributes into a likelihood-based community model without imposing an ordering on metadata values. It uses iterative posterior and parameter updates, with polynomial priors and probability constraints for ordered or continuous metadata extensions.

  • The model combines network adjacency data and metadata to estimate community assignments and parameter matrices by maximizing likelihood.
  • Jensen’s inequality converts the difficult likelihood maximization into alternating optimization over the posterior distribution q(s) and model parameters.The algorithm repeatedly updates q(s) and then Θ, Γ until convergence.
  • The method accelerates denominator calculations from n^2 terms to n by factorizing beliefs for distant nodes in large sparse networks.This factorization is unavailable for numerator terms involving adjacent-node beliefs.
  • After convergence, q(s) is the posterior distribution over community assignments given the network, parameters, and metadata.
  • For ordered metadata, the prior P(s|x) is represented with finite-degree basis functions, specifically polynomials, to enforce smoothness and limit overfitting.The paper notes that selecting the polynomial degree is an unresolved model-selection problem.
  • Bernstein-basis coefficients constrained to [0,1] produce valid community priors, and alternating coefficient updates converge to an optimal degree-N polynomial prior.

4. Implementation

The implementation uses repeated EM-style optimization and normalized mutual information to evaluate metadata–community agreement. It also adopts a symmetric normalization that reaches one when metadata perfectly predict community membership.

  • The algorithm’s running time is dominated by belief propagation, so early iterations avoid overly converged beliefs to improve speed.
  • The implementation limits EM iterations to 20 or 100 steps and discards runs that fail to converge within the allotted limit.Experiments with up to 1000 steps sometimes produced poorer synthetic-network results.
  • Normalized mutual information measures agreement between metadata and community divisions while remaining interpretable on a zero-to-one scale.
  • The chosen normalization uses the minimum of community and metadata entropies, making NMI symmetric and equal to one under perfect prediction.

Appendix C: Further examples

The appendix introduces additional applications and details, while collecting summary statistics for all studied networks in a single table.

  • Summary statistics for every network analyzed in the paper are reported in Table I.

1. Facebook friendship network

In the Harvard Facebook network, the method learns community priors from graduation year and dorm metadata. Year produces a clearer age-aligned division, while dorm correlates with communities less cleanly.

  • The FB100 data comprise separate college friendship networks whose nodes are students, edges are Facebook friendships, and metadata describe the students.
  • Harvard’s network contains 15 126 students spanning graduation years 2003 to 2009, with a small alumni population from 2000–2002.
  • Figure 4 displays learned community-membership priors for five-way divisions using graduation year in the top panel and dorm in the bottom panel.Colors encode prior probabilities across communities.
  • Treating year as unordered still yields communities aligned with age, with the figure’s bars summing to one across community probabilities.
  • Students without recorded year form a mixture of all five groups, while an additional blue group corresponds to alumni.
  • The year-based correlation is stronger and cleaner than the dorm-based correlation, although dorm still shows a clear relationship with community membership.

2. Malaria gene recombination network

The malaria gene recombination networks use sequence-derived Cys and CP labels as metadata for community analysis. Incorporating CP labels reveals cleaner community structure and exposes correlations with Cys labels across HVR 6 and HVR 5.

  • Biological network: P. falciparum var genes encode immunologically distinct proteins and frequently recombine by shuffling substrings.This recombination creates a bipartite gene–substring network, with HVRs defining distinct edge sets and gene–gene projections used for analysis.
  • Metadata: Cys and CP labels provide sequence-derived metadata, with Cys indicating two or four cysteines and CP subdividing Cys classes into six motif-based groups.The analysis uses CP labels as metadata for a two-way community division and evaluates correlations with Cys labels.
  • HVR 6: Without metadata, Cys labels mix across HVR 6 communities, whereas incorporating CP labels produces a nearly perfect partition.The result indicates that CP labels correlate well with HVR 6 community structure, revealing a relationship obscured without metadata.
  • HVR 6: The inferred HVR 6 communities predict Cys labels at 96% probability for two-cysteine genes and 67% probability for four-cysteine genes.These correlations connect motif-defined CP groups and network communities with cysteine counts and associated severe disease phenotypes.
  • HVR 5: Applying CP labels from HVR 6 to HVR 5 changes mixed Cys labels into a much cleaner HVR 5 community partition.This cross-region result supports the hypothesis that common constraints on recombination span distinct highly variable regions.
Loading 1507.04001v1…