"Non-Markovian Models of Opinion Dynamics on Temporal Networks"

One of my papers was published in final form today. Here are some details.

Title: Non-Markovian Models of Opinion Dynamics on Temporal Networks

Authors: Weiqi Chu and Mason A. Porter

Abstract: Traditional models of opinion dynamics, in which the nodes of a network change their opinions based on their interactions with neighboring nodes, consider how opinions evolve either on time-independent networks or on temporal networks with edges that follow Poisson statistics. Most such models are Markovian. However, in many real-life networks, interactions between individuals (and hence the edges of a network) follow non-Poisson processes and thus yield dynamics with memory-dependent effects. In this paper, we model opinion dynamics in which the entities of a temporal network interact and change their opinions via random social interactions. When the edges have non-Poisson interevent statistics, the corresponding opinion models have non-Markovian dynamics. We derive a family of opinion models that are induced by arbitrary waiting-time distributions (WTDs), and we illustrate a variety of induced opinion models from common WTDs (including Dirac delta distributions, exponential distributions, and heavy-tailed distributions). We analyze the convergence to consensus of these models and prove that homogeneous memory-dependent models of opinion dynamics in our framework always converge to the same steady state regardless of the WTD. We also conduct a numerical investigation of the effects of waiting-time distributions on both transient dynamics and steady states. We observe that models that are induced by heavy-tailed WTDs converge more slowly to a steady state than models that are induced by WTDs with light tails (or with compact support) and that entities with longer waiting times exert more influence on the mean opinion at steady state.

"Tie-Decay Networks in Continuous Timeand Eigenvector-Based Centralities"

The paper based on one of my old projects finally appeared in final form. Here are some details.

Title: Tie-Decay Networks in Continuous Timeand Eigenvector-Based Centralities

Authors: Walid Ahmad, Mason A. Porter, and Mariano Beguerisse-Díaz

Abstract: Network theory is a useful framework for studying interconnected systems of interacting entities. Many networked systems evolve continuously in time, but most existing methods for the analysis of time-dependent networks rely on discrete or discretized time. In this paper, we propose an approach for studying networks that evolve in continuous time by distinguishing between interactions, which we model as discrete contacts, and ties, which encode the strengths of relationships over time. To illustrate our tie-decay network formalism, we adapt the well-known PageRank centrality score to our tie-decay framework in a mathematically tractable and computationally efficient way. We apply this framework to a synthetic example and then use it to study a network of retweets during the 2012 National Health Service controversy in the United Kingdom. Our work also provides guidance for similar generalizations of other tools from network theory to continuous-time networks with tie decay, including for applications to streaming data.

"Models of Continuous-Time Networks with Tie Decay, Diffusion, and Convection"

Another of my papers just came out in final form today. Here are some details.

Title: Models of Continuous-Time Networks with Tie Decay, Diffusion, and Convection

Authors: Xinzhe Zuo and Mason A. Porter

Abstract: The study of temporal networks in discrete time has yielded numerous insights into time-dependent networked systems in a wide variety of applications. However, for many complex systems, it is useful to develop continuous-time models of networks and to compare them to associated discrete models. In this paper, we study several continuous-time network models and examine discrete approximations of them both numerically and analytically. To consider continuous-time networks, we associate each edge in a graph with a time-dependent tie strength that can take continuous non-negative values and decays in time after the most recent interaction. We investigate how the moments of the tie strength evolve with time in several models, and we explore—both numerically and analytically—criteria for the emergence of a giant connected component in some of these models. We also briefly examine the effects of the interaction patterns of continuous-time networks on the contagion dynamics of a susceptible–infected–recovered model of an infectious disease.

"Supracentrality Analysis of Temporal Networks with Directed Interlayer Coupling"

A new book chapter in the edited book Temporal Network Theory was just published in final form. Here are some details.

Titles: Supracentrality Analysis of Temporal Networks with Directed Interlayer Coupling

Authors: Dane Taylor, Mason A. Porter, and Peter J. Mucha

Abstract: We describe centralities in temporal networks using a supracentrality framework to study centrality trajectories, which characterize how the importances of nodes change in time. We study supracentrality generalizations of eigenvector-based centralities, a family of centrality measures for time-independent networks that includes PageRank, hub and authority scores, and eigenvector centrality. We start with a sequence of adjacency matrices, each of which represents a time layer of a network at a different point or interval of time. Coupling centrality matrices across time layers with weighted interlayer edges yields a supracentrality matrix ℂ(𝜔), where ω controls the extent to which centrality trajectories change over time. We can flexibly tune the weight and topology of the interlayer coupling to cater to different scientific applications. The entries of the dominant eigenvector of ℂ(𝜔) represent joint centralities, which simultaneously quantify the importance of every node in every time layer. Inspired by probability theory, we also compute marginal and conditional centralities. We illustrate how to adjust the coupling between time layers to tune the extent to which nodes’ centrality trajectories are influenced by the oldest and newest time layers. We support our findings by analysis in the limits of small and large ω.

"Neither Global nor Local: Heterogeneous Connectivity in Spatial Network Structures of World Migration"

One of my papers, which has had a DOI for about half a year, finally has its final publication coordinates. Notably, this is my first paper in a sociology journal. Here are some details.

Title: Neither Global nor Local: Heterogeneous Connectivity in Spatial Network Structures of World Migration

Authors: Valentin Danchev and Mason A. Porterc

Abstract: For a long time, geographic regions were considered the dominant spatial arbiter of international migration of people. However, since the late 1970s, many scholars have argued that movements reach beyond contiguous regions to connect distant, dispersed, and previously disconnected countries across the globe. The precise structure of world migration, however, remains an open question. We apply network analysis that incorporates spatial information to international migration-stock data to examine what multilateral structures of world migration have emerged from the interplay of regional concentration (local cohesion)and global interconnectedness (global cohesion) for the period 1960–2000. In the world migration network (WMN), nodes represent countries located in geographic space, and edges represent migrants froman origin country who live in a destination country during each decade. We characterize the large-scale structure and evolution of the WMN by algorithmically detecting international migration communities (i.e., sets of countries that are densely connected via migration) using a generalized modularity function for spatial, temporal, and directed networks. Our findings for the whole network suggest that movements in the WMN deviate significantly from the regional boundaries of the world and that international migration communities have become globally interconnected over time. However, we observe a strong variability in the distribution of strengths, neighborhood overlaps, and lengths of migration edges in the WMN. This manifests as three types of communities: global, local, and glocal. We find that long-distance movements in global communities bridge multiple non-contiguous countries, whereas local (and, to a lesser extent, glocal) communities remain trapped in contiguous geographic regions (or neighboring regions) for almost the whole period, contributing to a spatially fragmented WMN. Our findings demonstrate that world migration is neither regionally concentrated nor globally interconnected, but instead exhibits a heterogeneous connectivity pattern that channels unequal migration opportunities across the world.

"Eigenvector-Based Centrality Measures for Temporal Networks"

One of my papers came out in final published form yesterday. Here are the details.

Title: Eigenvector-Based Centrality Measures for Temporal Networks

Authors: Dane Taylor, Sean A. Myers, Aaron Clauset, Mason A. Porter, and Peter J. Mucha

Abstract: Numerous centrality measures have been developed to quantify the importances of nodes in time-independent networks, and many of them can be expressed as the leading eigenvector of some matrix. With the increasing availability of network data that changes in time, it is important to extend such eigenvector-based centrality measures to time-dependent networks. In this paper, we introduce a principled generalization of network centrality measures that is valid for any eigenvector-based centrality. We consider a temporal network with N nodes as a sequence of T layers that describe the network during diff erent time windows, and we couple centrality matrices for the layers into a supracentrality matrix of size NT x NT whose dominant eigenvector gives the centrality of each node i at each time t. We refer to this eigenvector and its components as a joint centrality, as it reflects the importances of both the node i and the time layer t. We also introduce the concepts of marginal and conditional centralities, which facilitate the study of centrality trajectories over time. We find that the strength of coupling between layers is important for determining multiscale properties of centrality, such as localization phenomena and the time scale of centrality changes. In the strong-coupling regime, we derive expressions for time-averaged centralities, which are given by the zeroth-order terms of a singular perturbation expansion. We also study first-order terms to obtain fi rst-order-mover scores, which concisely describe the magnitude of the nodes' centrality changes over time. As examples, we apply our method to three empirical temporal networks: the United States Ph.D. exchange in mathematics, costarring relationships among top-billed actors during the Golden Age of Hollywood, and citations of decisions from the United States Supreme Court.

"Time-Dependent Community Structure in Legislation Cosponsorship Networks in the Congress of the Republic of Peru"

One of my papers just came out in final form. (Also, you can download our data.) It has been available for quite a while in the journal, but we finally have our coordinates (page numbers, etc.). Here are the details.

Title: "Time-Dependent Community Structure in Legislation Cosponsorship Networks in the Congress of the Republic of Peru"

Authors: Sang Hoon Lee, José Manuel Magallanes, and Mason A. Porter

Abstract: We study community structure in time-dependent legislation cosponsorship networks in the Peruvian Congress, and we compare them briefly to legislation cosponsorship networks in the US Senate. To study these legislatures, we employ a multilayer representation of temporal networks in which legislators in each layer are connected to each other with a weight that is based on how many bills they cosponsor. We then use multilayer modularity maximization to detect communities in these networks. From our computations, we are able to capture power shifts in the Peruvian Congress during 2006–2011. For example, we observe the emergence of 'opportunists', who switch from one community to another, as well as cohesive legislative communities whose initial component legislators never change communities. Interestingly, many of the opportunists belong to the group that won the majority in Congress.

"Null Models for Community Detection in Spatially Embedded, Temporal Networks"

Another one of my papers finally got its volume, issue, and page numbers last week. (It came out in advanced access in November 2015.) I finally got my own copy of the document today, so here are some details.

Title: Null Models for Community Detection in Spatially Embedded, Temporal Networks

Authors: Marta Sarzynska, Elizabeth A. Leicht, Gerardo Chowell, and Mason A. Porter

Abstract: In the study of networks, it is often insightful to use algorithms to determine mesoscale features such as 'community structure', in which densely connected sets of nodes constitute 'communities' that have sparse connections to other communities. The most popular way of detecting communities algorithmically is to maximize the quality function known as modularity. When maximizing modularity, one compares the actual connections in a (static or time-dependent) network to the connections obtained from a random-graph ensemble that acts as a null model. The communities are then the sets of nodes that are connected to each other densely relative to what is expected from the null model. Clearly, the process of community detection depends fundamentally on the choice of the null model, so it is important to develop and analyse novel null models that take into account appropriate features of the system under study. In this paper, we investigate the effects of using null models that incorporate spatial information, and we propose a novel null model based on the radiation model of population spread. We also develop novel synthetic spatial benchmark networks in which the connections between entities are based on the distance or flux between nodes, and we compare the performance of static and time-dependent versions of the radiation null model to the standard ('Newman–Girvan') null model for modularity optimization and to a recently proposed gravity null model. In our comparisons, we use both the above synthetic benchmarks and time-dependent correlation networks that we construct using countrywide dengue fever incidence data for Peru. Our findings illustrate the need to use appropriate generative models for the development of spatial null models for community detection.

"Community Detection in Temporal Multilayer Networks, with an Application to Correlation Networks"

One of my papers was just published in final form a few days ago. As the title indicates, this paper concerns community detection in temporal multilayer networks. Here are the title, authors, and abstract.

Title: Community Detection in Temporal Multilayer Networks, with an Application to Correlation Networks

Authors: Marya Bazzi, Mason A. Porter, Stacy Williams , Mark McDonald, Daniel J. Fenn, and Sam D. Howison

Abstract: Abstract. Networks are a convenient way to represent complex systems of interacting entities. Many networks contain “communities” of nodes that are more densely connected to each other than to nodes in the rest of the network. In this paper, we investigate the detection of communities in temporal networks represented as multilayer networks. As a focal example, we study time-dependent financial-asset correlation networks. We first argue that the use of the "modularity" quality function –– which is defined by comparing edge weights in an observed network to expected edge weights in a "null network" –– is application-dependent. We differentiate between "null networks" and "null models" in our discussion of modularity maximization, and we highlight that the same null network can correspond to different null models. We then investigate a multilayer modularity-maximization problem to identify communities in temporal networks. Our multilayer analysis depends only on the form of the maximization problem and not on the specific quality function that one chooses. We introduce a diagnostic to measure persistence of community structure in a multilayer network partition. We prove several results that describe how the multilayer maximization problem measures a trade-off between static community structure within layers and larger values of persistence across layers. We also discuss some computational issues that the popular "Louvain" heuristic faces with temporal multilayer networks and suggest ways to mitigate them.

"Estimating Interevent Time Distributions from Finite Observation Periods in Communication Networks"

Here is the latest paper in my "please do this stuff more carefully" series.

People have been getting things wrong when it comes to examining inter-event time (IET) distributions, and there are methods from other fields (e.g., renewal processes) that allow one to correct for biases.

Here are the details of the paper.

Title: Estimating Interevent Time Distributions from Finite Observation Periods in Communication Networks

Authors: Mikko Kivelä and Mason A. Porter

Abstract: A diverse variety of processes––including recurrent disease episodes, neuron firing, and communication patterns among humans––can be described using interevent time (IET) distributions. Many such processes are ongoing, although event sequences are only available during a finite observation window. Because the observation time window is more likely to begin or end during long IETs than during short ones, the analysis of such data is susceptible to a bias induced by the finite observation period. In this paper, we illustrate how this length bias is born and how it can be corrected without assuming any particular shape for the IET distribution. To do this, we model event sequences using stationary renewal processes, and we formulate simple heuristics for determining the severity of the bias. To illustrate our results, we focus on the example of empirical communication networks, which are temporal networks that are constructed from communication events. The IET distributions of such systems guide efforts to build models of human behavior, and the variance of IETs is very important for estimating the spreading rate of information in networks of temporal interactions. We analyze several well-known data sets from the literature, and we find that the resulting bias can lead to systematic underestimates of the variance in the IET distributions and that correcting for the bias can lead to qualitatively different results for the tails of the IET distributions.

"Cross-Linked Structure of Network Evolution"

A new paper of mine was published in final form today. In this paper, my coauthors and I use a structure called a "cross-link" that connects a pair of time-dependent edges based on the similarity of their temporal evolution. In our study, the time-dependent edges arise from similarity of temporal dynamics of different nodes. The basic idea is to try to tease out when sets of edges evolve separately and when there is co-evolution. In this paper, we consider time-dependent networks that we construct from time series from functional brain networks and from output of coupled Kuramoto oscillators. Here are the details of the paper.


Title: Cross-Linked Structure of Network Evolution

Authors: Danielle S. Bassett, Nicholas F. Wymbs, Mason A. Porter, Peter J. Mucha, and Scott T. Grafton

Abstract: We study the temporal co-variation of network co-evolution via the cross-link structure of networks, for which we take advantage of the formalism of hypergraphs to map cross-link structures back to network nodes. We investigate two sets of temporal network data in detail. In a network of coupled nonlinear oscillators, hyperedges that consist of network edges with temporally co-varying weights uncover the driving co-evolution patterns of edge weight dynamics both within and between oscillator communities. In the human brain, networks that represent temporal changes in brain activity during learning exhibit early co-evolution that then settles down with practice. Subsequent decreases in hyperedge size are consistent with emergence of an autonomous subgraph whose dynamics no longer depends on other parts of the network. Our results on real and synthetic networks give a poignant demonstration of the ability of cross-link structure to uncover unexpected co-evolution attributes in both real and synthetic dynamical systems. This, in turn, illustrates the utility of analyzing cross-links for investigating the structure of temporal networks.

"Generalized Master Equations for Non-Poisson Dynamics on Networks"

Here is one of my papers that has just appeared in final form today:

Title: Generalized Master Equations for Non-Poisson Dynamics on Networks

Authors: Till Hoffmann, Mason A. Porter, and Renaud Lambiotte

Abstract: The traditional way of studying temporal networks is to aggregate the dynamics of the edges to create a static weighted network. This implicitly assumes that the edges are governed by Poisson processes, which is not typically the case in empirical temporal networks. Accordingly, we examine the effects of non-Poisson inter-event statistics on the dynamics of edges, and we apply the concept of a generalized master equation to the study of continuous-time random walks on networks. We show that this equation reduces to the standard rate equations when the underlying process is Poissonian and that its stationary solution is determined by an effective transition matrix whose leading eigenvector is easy to calculate. We conduct numerical simulations and also derive analytical results for the stationary solution under the assumption that all edges have the same waiting-time distribution. We discuss the implications of our work for dynamical processes on temporal networks and for the construction of network diagnostics that take into account their nontrivial stochastic nature.