Triad transition probabilities characterize complex networks
PDF version | Permalink
Complex networked systems are present in every aspect of our lives. Life itself is made possible by the intricate biological interactions within gene regulatory networks and food webs. Technological networks such as the Internet have changed the way the world seeks information and does business. And technology-enabled social networks have drastically altered how people meet and communicate. In general, complex networks feature large numbers of highly interconnected units exhibiting time-dependent behaviour. A relatively simple interactivity between neighbouring units may often compound into emergent collective behaviour of surprising sophistication. The need to analyse complex systems and to predict changes in them is crucial: from assessing the potential effects of human activity on food webs, to defining telecommunications service offerings according to expected user behaviour. Yet the scale, complexity and dynamics of today's technology-based complex networks have proven resistant to traditional network analysis methods. Predicting structural changes in such networks remains a challenge.
Self-organization, synchronization and other emergent phenomena of networked structures have been widely studied for many years, mainly via simulations and theoretical analysis. Unfortunately, this work often yields unsatisfactory real-world results. Most models addressing the growth of complex networks strive to reproduce certain global characteristics of those networks: e.g. node degree distribution,1 clustering coefficient2and network diameter.3 At the same time, models developed specifically for social networks naturally focus on features typical of those networks.4–8But both approaches tend to ignore the local structure of complex systems.
Inspired by the modern-day ‘data explosion,’9 we propose using data-driven techniques to infer dynamic structure from local characteristics. We start from the observation that the local topologies of social networks differ significantly from those of standard network models (see Figure 1). Indeed, when local topology is expressed in terms of network motifs (e.g. subgraphs containing three to seven nodes), self-evolving networks show visibly biased frequency distributions that contrast sharply with those of artificially generated networks. We then propose an approach toward quantifying network evolution schemes which, though rooted in graph analysis, uses inherent network dynamics, as revealed through observations across recorded history.
The smallest non-trivial subgraph of a network is a triad: a directed network of exactly three nodes. One technique for quantifying the connections within triads, called a triad census, involves slicing the history of the network into time windows, determining the configurations of multiple triads in each period and tallying the results. Since the three nodes in a triad form three pairs, and since each pair is able to connect in either, neither or both directions, there are 64 (=43) possible distinct triad configurations. (If no distinction is made among the three nodes, this number decreases to 16.) We propose an enhanced procedure called the Triad Transition Method,10–12in which the configurations of a large number of triads in the network are accumulated across successive time windows. Given any two possible triad configurations, the triad census is used to estimate the probability that a triad in the first configuration will transition to the second in the next time window. The resulting Triad Transition Matrix stores these probabilities for every possible before-and-after configuration pair.
Figure 2 presents the Triad Transition Method, broken down into individual steps. Although its statistical analysis of topological connection patterns assumes no a priori knowledge about the nature of relations among nodes, we find that its ability to predict link dynamics outperforms existing methods, especially in the case of sparse networks analysed across short timescales. Moreover, to the extent that the computed triad transition probabilities capture local connection pattern dynamics, the approach provides a useful tool for classifying distinct dynamic networks (social, biological etc.) according to the local evolutionary trajectories of a collection of nodes.
In real-world complex networks, global structure arises from local interaction patterns in a non-obvious way. The Triad Transition Method represents one of the first attempts to use historical data about local topology to predict global dynamics. As such, it may be seen as an initial step toward not only understanding and classifying these systems, but also predicting their evolution. Our future work on predictive methods will focus on considering the context of the analysed system and on non-structural network features. This will enable us to tighten the connection between machine learning, autonomy, predictive analytics and complex networked systems research.