PaperlayerView exact revision on arXiv

Source-linked AI summary

Using higher-order Markov models to reveal flow-based communities in networks

Vsevolod Salnikov, Michael T. Schaub, Renaud Lambiotte

arXiv:1601.03516v3physics.soc-phcs.SI

TL;DR

Simple Markov models omit history-dependent flows, which can matter in networked systems. This paper represents such memory with second-order Markov models and extends community-detection methods to those dynamics. Its examples show that memory-aware analysis can reveal flow communities shaped by temporal correlations and, in flight pathways, stronger community overlap than an expanded first-order model.

Abstract

from arXiv · show

Complex systems made of interacting elements are commonly abstracted as networks, in which nodes are associated with dynamic state variables, whose evolution is driven by interactions mediated by the edges. Markov processes have been the prevailing paradigm to model such a network-based dynamics, for instance in the form of random walks or other types of diffusions. Despite the success of this modelling perspective for numerous applications, it represents an over-simplification of several real-world systems. Importantly, simple Markov models lack memory in their dynamics, an assumption often not realistic in practice. Here, we explore possibilities to enrich the system description by means of second-order Markov models, exploiting empirical pathway information. We focus on the problem of community detection and show that standard network algorithms can be generalized in order to extract novel temporal information about the system under investigation. We also apply our methodology to temporal networks, where we can uncover communities shaped by the temporal correlations in the system. Finally, we discuss relations of the framework of second order Markov processes and the recently proposed formalism of using non-backtracking matrices for community detection.

INTRODUCTION

Simple Markov models cannot represent history-dependent flows, which occur in systems such as human mobility and communication. The paper extends network analysis to second-order dynamics, where states represent directed edges, and frames the approach through random walks and community detection.

INTRODUCTION

  • Network structure shapes random-walk dynamics, while spectral properties of the governing matrix can reveal structural organization such as modularity.The network-to-process correspondence also allows researchers to examine how topology influences dynamics [2].Source: INTRODUCTION · p. 2
  • Second-order models capture temporal path dependence that simple Markov models omit, with transition probabilities measurable from interaction pathways.The paper cites human mobility, web traffic, citation flows, and email cascades as examples.Source: INTRODUCTION · p. 2
  • In an M2 model, states are sequences of two nodes, equivalent to directed edges, so the memory network represents observed dynamics.Its structural properties can be studied using network-science tools.Source: INTRODUCTION · p. 2
  • The paper generalizes community-detection methods, including Markov stability, to M2 networks and connects the framework to non-backtracking methods.Because partitions of M2 states partition original edges, the approach can identify overlapping communities.Source: INTRODUCTION · p. 3

Random walks on directed networks

  • For directed networks, a walk’s stationary distribution is given by the dominant left eigenvector of the Laplacian and depends on global network properties.The paper handles non-ergodic real-world networks by using the largest strongly connected component or random teleportations, depending on network structure.Source: Random walks on directed networks · p. 3

Community structure from a dynamical viewpoint

Markov stability identifies communities as groups that retain random-walk flow over time. Its time scale controls the size of detected modules, and its flow-based interpretation distinguishes it from structural community methods.

Community structure from a dynamical viewpoint

  • Flow-retaining groups are dynamical communities, and optimizing persistence of diffusion within groups provides a partition quality function.This flow-based view differs from defining communities as densely or homogeneously connected substructures.Source: Community structure from a dynamical… · p. 4
  • At longer Markov times, walkers explore larger graph regions, so detected modules are generally larger; robust partitions can appear as plateaux across time.In the infinite-time limit, stability maximization yields a bipartition aligned with the normalized Fiedler eigenvector.Source: Community structure from a dynamical… · p. 4
  • Markov stability can be rewritten as modularity on a dynamics-weighted network, allowing modularity-based algorithms such as Louvain to optimize it.The new network weights connections according to their role in diffusion.Source: Community structure from a dynamical… · p. 4
  • For undirected networks, linearized stability recovers original-network modularity at t = 1 and a Potts-model heuristic at other times.For directed networks, the linearized expression is not equivalent to directed modularity of the original network.Source: Community structure from a dynamical… · p. 4
  • Markov-stability optimization inherits modularity’s resolution limit and degeneracy of optimal solutions, so partitions require careful interpretation.Sweeping resolution parameters and seeking robust partitions can circumvent some of these problems.Source: Community structure from a dynamical… · p. 5

From first to second order Markov models

Second-order dynamics can be represented as a first-order walk on a larger network whose states are directed edges. This representation lets Markov-stability analysis operate on memory-aware flows.

From first to second order Markov models

  • An M2 transition specifies the probability of moving from edge i→j to edge j→k, conditioned on the previous node i.The transition probabilities are normalized over possible next nodes.Source: From first to second order Markov models · p. 5
  • The second-order process is equivalent to a first-order Markov walk on a directed M2 network with 2M states for an undirected graph of M links.Each undirected link contributes two directed-edge states, one for each traversal direction.Source: From first to second order Markov models · p. 5
  • A continuous-time walk on the M2 network has a stationary distribution given by the left eigenvector of its Laplacian associated with eigenvalue 0.The state probability pα(t) is the probability of finding the walker on M2 node α at time t.Source: From first to second order Markov models · p. 5
  • The M1-expanded representation lifts ordinary first-order dynamics into the edge-based M2 state space, with stationary probabilities proportional to edge weights.For edge α, πα = wα/W, where W is the total edge weight.Source: From first to second order Markov models · p. 5

Models of second-order Markov processes

When pathway statistics are unavailable, a parameterized memory model can construct M2 networks from aggregated network information. It weights three kinds of transitions between directed edges.

Models of second-order Markov processes

  • When only an aggregated network is available, an M2 model can be built using a memory model calibrated from pathway statistics in similar datasets.The paper gives fitting parameters from one email dataset as an example for generating a model for another email network.Source: Models of second-order Markov processes · pp. 5–6
  • The memory model distinguishes return, triangular, and exploratory steps between directed edges, weighted by r2, r3, and r>3.These correspond respectively to returning to the prior node, taking a triangle-forming step, and moving to an endpoint that is neither the prior node nor its neighbor.Source: Models of second-order Markov processes · p. 6
  • The weighted adjacency matrix is normalized row-wise to obtain the second-order transition matrix.The construction combines separate return, triangular, and exploratory adjacency matrices.Source: Models of second-order Markov processes · p. 6
  • Equal transition weights make the projected node-space dynamics first-order, while strictly positive weights preserve ergodicity when it holds for the graph.The parameters are r2, r3, and r>3.Source: Models of second-order Markov processes · p. 6

Higher order Markov dynamics reveal communities in a network of flight pathways

The flight-pathway analysis compares communities from three Markov representations of the same mobility data. Second-order dynamics yield more overlapping airport communities than the expanded first-order model, while the fitted M2model is intermediate.

Higher order Markov dynamics reveal communities in a network of flight pathways

  • The analysis compares edge communities from M1expanded, empirical M2 transitions, and fitted M2model transitions, restricting nodes to the intersection of their largest strongly connected components.The shared-node restriction ensures stability is well-defined for all three processes.Source: Higher order Markov dynamics reveal… · p. 8
  • At Markov time t = 1, normalized variation of information is 0.42 for M2 versus M1expanded, 0.36 for M2 versus M2model, and 0.38 for M1expanded versus M2model.M2model is an intermediate clustering solution and requires far fewer parameters than M2.Source: Higher order Markov dynamics reveal… · p. 8
  • Airport participation entropy is calculated from the fractions of incident edges assigned to each community.Entropy zero indicates association with a single community; higher values indicate more diverse participation.Source: Higher order Markov dynamics reveal… · p. 8
  • M2 yields more overlapping airport communities than M1expanded, while M2model has intermediate participation entropy.The comparison uses the distributions of airport community-participation entropy.Source: Figure 3 · p. 7, Higher order Markov dynamics reveal… · p. 8

Second-order Markov models of time-stamped temporal networks

Time-stamped networks can be represented by second-order Markov dynamics to capture flow constraints that static aggregation or window-by-window tracking may miss. The approach constructs edge-state transitions from simulated trajectories, with timing sensitivity depending on walker and event persistence.

Second-order Markov models of time-stamped temporal networks

  • Second-order representations capture temporal constraints on flow, including causal paths and synchrony between neighboring edge activations.This offers a third notion of temporal community, distinct from static aggregation and tracking communities across time windows.Source: Second-order Markov models of… · p. 8
  • For sufficiently persistent active groups, M2 community detection recovers the planted three-group organization, with a plateau at Markov times slightly above t = 1.In the example, group persistence is controlled by pk and recovery occurs when it is sufficiently large.Source: Figure 4 · p. 9
  • The temporal network is aggregated into Astatic, whose directed edges become M2 states; simulated walker trajectories then supply transition frequencies between edge pairs.The walker waits for an available edge, leaves with probability 1−ps, and otherwise stays at its node.Source: Second-order Markov models of… · pp. 8–9
  • As ps increases, the original event ordering matters less and the influence of exact timing is expected to be diluted.Other pathway-generation procedures could also be used, including accounting for interval durations or varying the leaving probability with available contacts.Source: Second-order Markov models of… · p. 9

Community detection in M2 networks constructed from temporal data: an illustrative example

A synthetic temporal network tests whether M2 communities recover groups of edges that activate together. Recovery depends on how long each active group persists, with no structure in the rapidly switching limit.

Community detection in M2 networks constructed from temporal data: an illustrative example

  • The benchmark is a complete directed social network with g non-overlapping interaction types; at each time, all edges of one group are active, and that group persists with probability pk.For N = 10 and g = 3, the walker has three outgoing edges available at each step.Source: Community detection in M2 networks… · p. 9
  • The trajectory-generating walker uses ps = 0 because changing its node-staying probability is effectively equivalent to changing pk in this example.This is the stated simplifying choice for the benchmark.Source: Community detection in M2 networks… · pp. 9–10
  • The planted groups are recovered with high accuracy for Markov times slightly above t = 1 when pk is sufficiently large, with a transition around pk = 0.4.At pk = 0, the dynamics average to a first-order walk on a fully connected network, while pk = 1 is a trivial fixed-group case.Source: Community detection in M2 networks… · p. 10

A real-world case study: analyzing temporal interaction pattern of school children

In school contact data, second-order analysis finds both class-aligned partitions and smaller-time communities associated with lunch-break interactions. The latter are not detected from the aggregated network or the memoryless expanded representation.

A real-world case study: analyzing temporal interaction pattern of school children

  • The dataset contains 77,602 face-to-face contact events among 242 children and teachers across two consecutive days.The contacts were captured by wireless wearable sensors in a primary school.Source: A real-world case study: analyzing… · p. 10
  • At tC=10 ≈0.631, the algorithm robustly detects 10 communities overlapping the students' 10 classes, although the aggregated weighted network also reveals the class partition.The class partition is therefore not unique to the second-order analysis.Source: A real-world case study: analyzing… · p. 10
  • At Markov time t = 0.56, M2 identifies 15 communities, including lunch-break interaction groups that aggregation and M1expanded do not detect.These temporally localized modules mix students from different classes and are distinct from persistent structural communities.Source: A real-world case study: analyzing… · p. 10

SECOND-ORDER MODELS, NON-BACKTRACKING WALKS AND SPECTRAL CLUSTERING

Non-backtracking walks are a special case of second-order memory dynamics, linking memory transition matrices to spectral clustering. The comparisons show how memory settings relate to clustering performance, while the school-network analysis illustrates temporal communities that aggregation can miss.

SECOND-ORDER MODELS, NON-BACKTRACKING WALKS AND SPECTRAL CLUSTERING

  • Non-backtracking walks forbid an immediate return to the node just left, and their matrix is a degree-scaled transition matrix for a special second-order memory walk.The non-backtracking transition matrix is one point in a continuum of memory transition matrices whose parameters can be varied for spectral clustering.Source: SECOND-ORDER MODELS, NON-BACKTRACKING… · pp. 10–11
  • At Markov time t = 0.56, the school M2 network has 15 communities: 10 concentrated in single classes and five synchronized lunchtime groups spanning classes.The lunchtime communities represent interactions between students from different classes.Source: Figure 5 · p. 11
  • For sparse networks, spectral clustering with B performs clearly better than with A or L, while T (r2 = 0, r3 = 1, r>3 = 1) performs almost as well as B and slightly better at c ≈ 8.The comparison uses planted bipartitions and NMI; the plotted average-degree range includes the theoretical detectability limit c* ≈ 3.45.Source: SECOND-ORDER MODELS, NON-BACKTRACKING… · p. 12, Figure 6 · p. 12
  • Increasing the weight assigned to exploratory steps appears to make node groupings easier to determine, but adding memory can also be detrimental to hard clustering.The experiment assumes a known bipartition of equally sized groups and evaluates non-overlapping node clusters.Source: SECOND-ORDER MODELS, NON-BACKTRACKING… · p. 12
  • In sparse graphs, local bottlenecks can localize diffusion, so the second eigenvector may reflect local obstacles rather than separation between planted communities.The paper relates strong local flow constraints to substantial return flow in reported memory dynamics.Source: SECOND-ORDER MODELS, NON-BACKTRACKING… · p. 13

CONCLUSIONS

The paper extends flow-based community detection to second-order Markov dynamics, representing transitions between directed edges. This yields edge partitions interpretable as overlapping node communities, and the tested applications recover temporal patterns that aggregated first-order models miss.

CONCLUSIONS

  • Second-order Markov dynamics support flow-based community detection by extending Markov stability and related techniques to transitions between directed edges.The framework includes approaches such as Potts models and spectral clustering.Source: CONCLUSIONS · p. 13
  • Clustering edges in the second-order model can be interpreted as overlapping communities of nodes in the original network.The paper identifies this as a beneficial feature of the approach.Source: CONCLUSIONS · p. 13
  • In the flight and school-network cases, even approximate second-order dynamics recovered temporal patterns that an aggregated first-order model would miss.The paper uses a model calibrated from similar datasets for flight pathways and represents temporal school data as a second-order network.Source: CONCLUSIONS · p. 13
  • Second-order models increase computational cost because their state count equals the number of directed edges, and pathway statistics may not be readily accessible.The paper presents a calibrated pathway model and a temporal-network representation as strategies for these practical concerns.Source: CONCLUSIONS · p. 13
  • The non-backtracking matrix is a scaled version of a non-backtracking random walk's transition matrix, a special case of the second-order dynamics considered here.Further investigation of second-order processes and their relation to spectral clustering is left for future work.Source: CONCLUSIONS · p. 13

Related papers

Loading 1601.03516v3…