Source-linked AI summary
Components in time-varying graphs
V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, V. Latora
TL;DR
Static graph analysis can discard the timing and ordering of interactions in inherently time-varying systems. The paper defines temporal connectedness and components, maps strong-component discovery to maximal cliques in an affine graph, and reports that temporal analysis captures structure missed by aggregation, including variable node component sizes.
Problem
Static graph methods aggregate time-varying interactions as concurrent and therefore neglect link timing, duration, frequency, and temporal correlations.
Method
The paper represents networks as time-ordered graph sequences, defines temporal node and graph components, and maps strong-component discovery to maximal cliques in an affine graph.
Results
Temporal component analysis of three human-interaction datasets reveals substantial variability in node temporal in- and out-components that static analysis cannot detect.
Takeaways & Limitations
Accounting for time in graph components captures important features of real systems that remain hidden in static graph analysis.
Abstract
from arXiv · showhide
Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, it is today possible to produce and analyze social and biological networks with detailed information on the time of occurrence and duration of each link. However, standard graph metrics introduced so far in complex network theory are mainly suited for static graphs, i.e., graphs in which the links do not change over time, or graphs built from time-varying systems by aggregating all the links as if they were concurrent in time. In this paper, we extend the notion of connectedness, and the definitions of node and graph components, to the case of time-varying graphs, which are represented as time-ordered sequences of graphs defined over a fixed set of nodes. We show that the problem of finding strongly connected components in a time-varying graph can be mapped into the problem of discovering the maximal-cliques in an opportunely constructed static graph, which we name the affine graph. It is therefore an NP-complete problem. As a practical example, we have performed a temporal component analysis of time-varying graphs constructed from three data sets of human interactions. The results show that taking time into account in the definition of graph components allows to capture important features of real systems. In particular, we observe a large variability in the size of node temporal in- and out-components. This is due to intrinsic fluctuations in the activity patterns of individuals, which cannot be detected by static graph analysis.
I. INTRODUCTION
The paper addresses the mismatch between inherently time-varying networks and static graph analysis, which aggregates interactions and discards their temporal ordering. It generalizes connectedness and graph components to time-varying graphs and links the resulting component problem to maximal cliques.
- Static graph analyses treat changing or aggregated links as concurrent, neglecting the temporal ordering and correlations of interactions.
- Connectedness and component concepts are generalized to time-varying graphs to reveal network structure that static analysis can leave hidden.
- The paper defines temporal node and graph components, maps time-varying component discovery to maximal cliques in an affine graph, and proves strong-component discovery NP-complete.
II. COMPONENTS IN STATIC GRAPHS
The paper reviews connectedness and component structure in static directed graphs, distinguishing weak and strong reachability and the node-level components derived from them.
- Directed graphs distinguish weak connectedness from strong connectedness because reachability from one node does not imply reachability in the reverse direction.
- A node’s out-component contains nodes it can reach, while its in-component contains nodes that can reach it.
- Weakly connected components use paths in the underlying undirected graph, whereas strongly connected components require directed paths in both directions.
- Weak and strong connectedness are equivalence relations in static directed graphs, allowing graph components to be defined from node-associated components.
- A strongly connected component can be obtained as the intersection of a node’s in-component and out-component.
III. COMPONENTS IN TIME-VARYING GRAPHS
The paper defines temporal reachability and extends node and graph components to time-varying graphs represented by ordered graph sequences. Temporal strong connectedness is symmetric but not transitive, requiring direct pairwise checks for component membership.
- A time-varying graph is an ordered sequence of graphs over fixed nodes, with each graph recording the network state at a specific time.
- Temporal reachability requires a walk whose contact times increase, so paths depend on the order in which links appear.
- Aggregating links can create paths absent from the temporal graph; in the example, node 5 reaches node 1 temporally, but node 1 cannot reach node 5.
- Temporal strong connectedness requires reachability in both directions, but it is not transitive, unlike strong connectedness in static graphs.
- Because pairwise temporal connectedness is not an equivalence relation, temporal graph components require every node in the set to connect strongly or weakly to every other node.
- Temporal node components include in-, out-, weakly connected, and strongly connected sets defined through temporal reachability.
IV. THE AFFINE GRAPH OF A TIME-VARYING GRAPH
The paper represents temporal strong connectedness with an undirected static affine graph, whose maximal cliques correspond to temporal strongly connected components. This mapping makes component discovery computationally difficult and can yield multiple valid component partitions.
- The affine graph is constructed by linking two nodes exactly when they are temporally strongly connected in both directions.It can be obtained from temporal shortest paths or node out-components.
- For the example, the affine graph has seven of ten possible links, representing strong connectedness between node pairs.The corresponding maximal-clique partitions include {1, 2, 3} with {4, 5}, or {2, 4, 5} with {1, 3}.
- Maximal cliques in the affine graph correspond to temporal strongly connected components, while maximum cliques identify the largest such components.The affine graph links pairs of nodes that are strongly connected in the time-varying graph.
- Ignoring temporal ordering makes the aggregated graph appear to have one connected component containing all five nodes, unlike the temporal analysis.The temporal graph instead admits two minimal partitions into nondegenerate strongly connected components.
- Finding all temporal strongly connected components is computationally hard because it reduces to enumerating maximal cliques and minimum clique covers.Listing maximal cliques has exponential complexity, and a time-varying graph may have multiple valid component partitions.
V. RESULTS
Temporal component analysis across three human-interaction datasets reveals strong dependence on time ordering, temporal scale, and activity patterns that static aggregation can obscure.
- The analysis used Bluetooth-based co-location graphs, hourly message-contact graphs, and three temporal social-network datasets spanning Reality Mining, INFOCOM, and Facebook.Reality Mining captured recurrent face-to-face interactions, INFOCOM bursty meeting interactions, and Facebook online communication.
- Temporal in- and out-component sizes varied markedly across individuals during the week, whereas aggregated static graphs produced a single giant connected component.Beginning-of-week interactions were more broadly connected, while end-of-week interactions occurred more within small groups.
- Reality Mining showed substantial daily fluctuations, with links ranging from 105 to 1485 and triangles ranging from 307 to 22096 across Mondays.These fluctuations reflected peculiar temporal connection patterns, including skipped classes and public holidays.
- At the weekly scale in Reality Mining, average maximal-clique size ranged from 39.3 to 62.5, while the number of strongly connected components stayed near 10.The largest strongly connected component depends on the affine graph's actual link and triangle configuration and on the temporal observation scale.
- For conference interactions, the largest strongly connected component reached S = 72 at 13:00, then declined to S = 46 by 20:00 as links and triangles decreased.At the hourly scale, S correlated clearly with the static comparison C, and the average strongly connected component size was comparable with the largest one.
- Less than 0.15% of Facebook users were mutually reachable temporally over adjacent weeks, versus at least 32% in the corresponding static giant component.This contrast demonstrates the substantial overestimation produced by static aggregation.
VI. CONCLUSIONS
The paper extends connectedness and component definitions to time-varying graphs by incorporating temporal link information such as duration, appearance times, and correlations.
- Temporal components incorporate link duration, appearance times, and temporal correlations rather than relying only on aggregate topology.
- The framework extends connectedness and node and graph component definitions from static to time-varying graphs.
- These definitions address information neglected by conventional static connectedness and component measures.