Catalog footprint

What is connected

38works
26topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

38 published item(s)

preprint2022arXiv

One Node at a Time: Node-Level Network Classification

Network classification aims to group networks (or graphs) into distinct categories based on their structure. We study the connection between classification of a network and of its constituent nodes, and whether nodes from networks in different groups are distinguishable based on structural node characteristics such as centrality and clustering coefficient. We demonstrate, using various network datasets and random network models, that a classifier can be trained to accurately predict the network category of a given node (without seeing the whole network), implying that complex networks display distinct structural patterns even at the node level. Finally, we discuss two applications of node-level network classification: (i) whole-network classification from small samples of nodes, and (ii) network bootstrapping.

preprint2022arXiv

Synchronization of coupled Kuramoto oscillators competing for resources

Populations of oscillators are present throughout nature. Very often synchronization is observed in such populations if they are allowed to interact. A paradigmatic model for the study of such phenomena has been the Kuramoto model. However, considering real oscillations are rarely isochronous as a function of energy, it is natural to extend the model by allowing the natural frequencies to vary as a function of some dynamical resource supply. Beyond just accounting for a dynamical supply of resources, however, competition over a \emph{shared} resource supply is important in a variety of biological systems. In neuronal systems, for example, resource competition enables the study of neural activity via fMRI. It is reasonable to expect that this dynamical resource allocation should have consequences for the synchronization behavior of the brain. This paper presents a modified Kuramoto dynamics which includes additional dynamical terms that provide a relatively simple model of resource competition among populations of Kuramoto oscillators. We design a mutlilayer system which highlights the impact of the competition dynamics, and we show that in this designed system, correlations can arise between the synchronization states of two populations of oscillators which share no phase-coupling edges. These correlations are interesting in light of the often observed variance between functional and structural connectivity measures in real systems. The model presented here then suggests that some of the observed discrepancy may be explained by the way in which the brain dynamically allocates resources to different regions according to demand. If true, models such as this one provide a theoretical framework for analyzing the differences between structural and functional measures, and possibly implicate dynamical resource allocation as an integral part of the neural computation process.

preprint2020arXiv

Tunable Eigenvector-Based Centralities for Multiplex and Temporal Networks

Characterizing the importances (i.e., centralities) of nodes in social, biological, and technological networks is a core topic in both network science and data science. We present a linear-algebraic framework that generalizes eigenvector-based centralities, including PageRank and hub/authority scores, to provide a common framework for two popular classes of multilayer networks: multiplex networks (which have layers that encode different types of relationships) and temporal networks (in which the relationships change over time). Our approach involves the study of joint, marginal, and conditional "supracentralities" that one can calculate from the dominant eigenvector of a supracentrality matrix [Taylor et al., 2017], which couples centrality matrices that are associated with individual network layers. We extend this prior work (which was restricted to temporal networks with layers that are coupled by adjacent-in-time coupling) by allowing the layers to be coupled through a (possibly asymmetric) interlayer-adjacency matrix $\tilde{\bf A}$, where the entry $\tilde{A}_{tt'} \geq 0$ encodes the coupling between layers $t$ and $t'$. Our framework provides a unifying foundation for centrality analysis of multiplex and temporal networks; it also illustrates a complicated dependency of the supracentralities on the topology and weights of interlayer coupling. By scaling $\tilde{\bf A}$ by an interlayer-coupling strength $ω\ge0$ and developing a singular perturbation theory for the limits of weak ($ω\to0^+$) and strong coupling ($ω\to\infty$), we also reveal an interesting dependence of supracentralities on the dominant left and right eigenvectors of $\tilde{\bf A}$.

preprint2019arXiv

Local Symmetry and Global Structure in Adaptive Voter Models

Adaptive voter models (AVMs) are simple mechanistic systems that model the emergence of mesoscopic structure from local networked processes driven by conflict and homophily. AVMs display rich behavior, including a phase transition from a fully-fragmented regime of "echo-chambers" to a regime of persistent disagreement governed by low-dimensional quasistable manifolds. Many extant methods for approximating the behavior of AVMs are either restricted in scope, expensive in computation, or inaccurate in predicting important statistics. In this work, we develop a novel, second-order moment closure approximation method for binary-state rewire-to-random and rewire-to-same model variants. We incorporate a small amount of noise via a random mutation term, which renders the system ergodic. Using ergodicity, we then approximate the voting process, which is non-Markovian in the second moments of the system, with a Markovian term near the phase transition. This approximation exploits an asymmetry between different classes of voting events. The resulting scheme enables us to predict the location of the phase transition and the active edge density in the regime of persistent disagreement, across the entire space of parameters and opinion densities. Numerically, our results are nearly exact for the rewire-to-random model, and competitive with other current approaches for the rewire-to-same model. Moreover, our computations display constant scaling in the mean degree, enabling approximations for denser systems than previously possible. We conclude with suggestions for model refinements and extensions.

preprint2016arXiv

A Local Perspective on Community Structure in Multilayer Networks

The analysis of multilayer networks is among the most active areas of network science, and there are now several methods to detect dense "communities" of nodes in multilayer networks. One way to define a community is as a set of nodes that trap a diffusion-like dynamical process (usually a random walk) for a long time. In this view, communities are sets of nodes that create bottlenecks to the spreading of a dynamical process on a network. We analyze the local behavior of different random walks on multiplex networks (which are multilayer networks in which different layers correspond to different types of edges) and show that they have very different bottlenecks that hence correspond to rather different notions of what it means for a set of nodes to be a good community. This has direct implications for the behavior of community-detection methods that are based on these random walks.

preprint2016arXiv

Eigenvector-Based Centrality Measures for Temporal Networks

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 different time windows, and we couple centrality matrices for the layers into a supra-centrality matrix of size NTxNT 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 first-order-mover scores, which concisely describe the magnitude of 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.

preprint2016arXiv

Enhanced detectability of community structure in multilayer networks through layer aggregation

Many systems are naturally represented by a multilayer network in which edges exist in multiple layers that encode different, but potentially related, types of interactions, and it is important to understand limitations on the detectability of community structure in these networks. Using random matrix theory, we analyze detectability limitations for multilayer (specifically, multiplex) stochastic block models (SBMs) in which L layers are derived from a common SBM. We study the effect of layer aggregation on detectability for several aggregation methods, including summation of the layers' adjacency matrices for which we show the detectability limit vanishes as O(L^{-1/2}) with increasing number of layers, L. Importantly, we find a similar scaling behavior when the summation is thresholded at an optimal value, providing insight into the common - but not well understood - practice of thresholding pairwise-interaction data to obtain sparse network representations.

preprint2016arXiv

Feature-Based Classification of Networks

Network representations of systems from various scientific and societal domains are neither completely random nor fully regular, but instead appear to contain recurring structural building blocks. These features tend to be shared by networks belonging to the same broad class, such as the class of social networks or the class of biological networks. At a finer scale of classification within each such class, networks describing more similar systems tend to have more similar features. This occurs presumably because networks representing similar purposes or constructions would be expected to be generated by a shared set of domain specific mechanisms, and it should therefore be possible to classify these networks into categories based on their features at various structural levels. Here we describe and demonstrate a new, hybrid approach that combines manual selection of features of potential interest with existing automated classification methods. In particular, selecting well-known and well-studied features that have been used throughout social network analysis and network science and then classifying with methods such as random forests that are of special utility in the presence of feature collinearity, we find that we achieve higher accuracy, in shorter computation time, with greater interpretability of the network classification results.

preprint2016arXiv

Transitivity reinforcement in the coevolving voter model

One of the fundamental structural properties of many networks is triangle closure. Whereas the influence of this transitivity on a variety of contagion dynamics has been previously explored, existing models of coevolving or adaptive network systems use rewiring rules that randomize away this important property. In contrast, we study here a modified coevolving voter model dynamics that explicitly reinforces and maintains such clustering. Employing extensive numerical simulations, we establish that the transitions and dynamical states observed in coevolving voter model networks without clustering are altered by reinforcing transitivity in the model. We then use a semi-analytical framework in terms of approximate master equations to predict the dynamical behaviors of the model for a variety of parameter settings.

preprint2015arXiv

Clustering Network Layers With the Strata Multilayer Stochastic Block Model

Multilayer networks are a useful data structure for simultaneously capturing multiple types of relationships between a set of nodes. In such networks, each relational definition gives rise to a layer. While each layer provides its own set of information, community structure across layers can be collectively utilized to discover and quantify underlying relational patterns between nodes. To concisely extract information from a multilayer network, we propose to identify and combine sets of layers with meaningful similarities in community structure. In this paper, we describe the "strata multilayer stochastic block model'' (sMLSBM), a probabilistic model for multilayer community structure. The central extension of the model is that there exist groups of layers, called "strata'', which are defined such that all layers in a given stratum have community structure described by a common stochastic block model (SBM). That is, layers in a stratum exhibit similar node-to-community assignments and SBM probability parameters. Fitting the sMLSBM to a multilayer network provides a joint clustering that yields node-to-community and layer-to-stratum assignments, which cooperatively aid one another during inference. We describe an algorithm for separating layers into their appropriate strata and an inference technique for estimating the SBM parameters for each stratum. We demonstrate our method using synthetic networks and a multilayer network inferred from data collected in the Human Microbiome Project.

preprint2015arXiv

Network Structure and Biased Variance Estimation in Respondent Driven Sampling

This paper explores bias in the estimation of sampling variance in Respondent Driven Sampling (RDS). Prior methodological work on RDS has focused on its problematic assumptions and the biases and inefficiencies of its estimators of the population mean. Nonetheless, researchers have given only slight attention to the topic of estimating sampling variance in RDS, despite the importance of variance estimation for the construction of confidence intervals and hypothesis tests. In this paper, we show that the estimators of RDS sampling variance rely on a critical assumption that the network is First Order Markov (FOM) with respect to the dependent variable of interest. We demonstrate, through intuitive examples, mathematical generalizations, and computational experiments that current RDS variance estimators will always underestimate the population sampling variance of RDS in empirical networks that do not conform to the FOM assumption. Analysis of 215 observed university and school networks from Facebook and Add Health indicates that the FOM assumption is violated in every empirical network we analyze, and that these violations lead to substantially biased RDS estimators of sampling variance. We propose and test two alternative variance estimators that show some promise for reducing biases, but which also illustrate the limits of estimating sampling variance with only partial information on the underlying population social network.

preprint2015arXiv

Topological data analysis of contagion maps for examining spreading processes on networks

Social and biological contagions are influenced by the spatial embeddedness of networks. Historically, many epidemics spread as a wave across part of the Earth's surface; however, in modern contagions long-range edges -- for example, due to airline transportation or communication media -- allow clusters of a contagion to appear in distant locations. Here we study the spread of contagions on networks through a methodology grounded in topological data analysis and nonlinear dimension reduction. We construct "contagion maps" that use multiple contagions on a network to map the nodes as a point cloud. By analyzing the topology, geometry, and dimensionality of manifold structure in such point clouds, we reveal insights to aid in the modeling, forecast, and control of spreading processes. Our approach highlights contagion maps also as a viable tool for inferring low-dimensional structure in networks.

preprint2014arXiv

A testing based extraction algorithm for identifying significant communities in networks

A common and important problem arising in the study of networks is how to divide the vertices of a given network into one or more groups, called communities, in such a way that vertices of the same community are more interconnected than vertices belonging to different ones. We propose and investigate a testing based community detection procedure called Extraction of Statistically Significant Communities (ESSC). The ESSC procedure is based on $p$-values for the strength of connection between a single vertex and a set of vertices under a reference distribution derived from a conditional configuration network model. The procedure automatically selects both the number of communities in the network and their size. Moreover, ESSC can handle overlapping communities and, unlike the majority of existing methods, identifies "background" vertices that do not belong to a well-defined community. The method has only one parameter, which controls the stringency of the hypothesis tests. We investigate the performance and potential use of ESSC and compare it with a number of existing methods, through a validation study using four real network data sets. In addition, we carry out a simulation study to assess the effectiveness of ESSC in networks with various types of community structure, including networks with overlapping communities and those with background vertices. These results suggest that ESSC is an effective exploratory tool for the discovery of relevant community structure in complex network systems. Data and software are available at \urlhttp://www.unc.edu/~jameswd/research.html.

preprint2014arXiv

Cross-Linked Structure of Network Evolution

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, and 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.

preprint2014arXiv

Dynamics on Modular Networks with Heterogeneous Correlations

We develop a new ensemble of modular random graphs in which degree-degree correlations can be different in each module and the inter-module connections are defined by the joint degree-degree distribution of nodes for each pair of modules. We present an analytical approach that allows one to analyze several types of binary dynamics operating on such networks, and we illustrate our approach using bond percolation, site percolation, and the Watts threshold model. The new network ensemble generalizes existing models (e.g., the well-known configuration model and LFR networks) by allowing a heterogeneous distribution of degree-degree correlations across modules, which is important for the consideration of nonidentical interacting networks.

preprint2014arXiv

Kantian fractionalization predicts the conflict propensity of the international system

The study of complex social and political phenomena with the perspective and methods of network science has proven fruitful in a variety of areas, including applications in political science and more narrowly the field of international relations. We propose a new line of research in the study of international conflict by showing that the multiplex fractionalization of the international system (which we label Kantian fractionalization) is a powerful predictor of the propensity for violent interstate conflict, a key indicator of the system's stability. In so doing, we also demonstrate the first use of multislice modularity for community detection in a multiplex network application. Even after controlling for established system-level conflict indicators, we find that Kantian fractionalization contributes more to model fit for violent interstate conflict than previously established measures. Moreover, evaluating the influence of each of the constituent networks shows that joint democracy plays little, if any, role in predicting system stability, thus challenging a major empirical finding of the international relations literature. Lastly, a series of Granger causal tests shows that the temporal variability of Kantian fractionalization is consistent with a causal relationship with the prevalence of conflict in the international system. This causal relationship has real-world policy implications as changes in Kantian fractionalization could serve as an early warning sign of international instability.

preprint2014arXiv

Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks

It is common in the study of networks to investigate meso-scale features to try to gain an understanding of network structure and function. For example, numerous algorithms have been developed to try to identify "communities," which are typically construed as sets of nodes with denser connections internally than with the remainder of a network. In this paper, we adopt a complementary perspective that "communities" are associated with bottlenecks of locally-biased dynamical processes that begin at seed sets of nodes, and we employ several different community-identification procedures (using diffusion-based and geodesic-based dynamics) to investigate community quality as a function of community size. Using several empirical and synthetic networks, we identify several distinct scenarios for ``size-resolved community structure'' that can arise in real (and realistic) networks. Depending on which scenario holds, one may or may not be able to successfully identify ``good'' communities in a given network, the manner in which different small communities fit together to form meso-scale network structures can be very different, and processes such as viral propagation and information diffusion can exhibit very different dynamics.In addition, our results suggest that, for many large realistic networks, the output of locally-biased methods that focus on communities that are centered around a given seed node might have better conceptual grounding and greater practical utility than the output of global community-detection methods. They also illustrate subtler structural properties that are important to consider in the development of better benchmark networks to test methods for community detection. [Note: Because of space limitations in the arXiv's abstract field, this is an abridged version of the paper's abstract.]

preprint2013arXiv

A multi-opinion evolving voter model with infinitely many phase transitions

We consider an idealized model in which individuals' changing opinions and their social network coevolve, with disagreements between neighbors in the network resolved either through one imitating the opinion of the other or by reassignment of the discordant edge. Specifically, an interaction between $x$ and one of its neighbors $y$ leads to $x$ imitating $y$ with probability $(1-α)$ and otherwise (i.e., with probability $α$) $x$ cutting its tie to $y$ in order to instead connect to a randomly chosen individual. Building on previous work about the two-opinion case, we study the multiple-opinion situation, finding that the model has infinitely many phase transitions. Moreover, the formulas describing the end states of these processes are remarkably simple when expressed as a function of $β= α/(1-α)$.

preprint2013arXiv

Fluctuation of similarity (FLUS) to detect transitions between distinct dynamical regimes in short time series

Recently a method which employs computing of fluctuations in a measure of nonlinear similarity based on local recurrence properties in a univariate time series, was introduced to identify distinct dynamical regimes and transitions between them in a short time series [1]. Here we present the details of the analytical relationships between the newly introduced measure and the well known concepts of attractor dimensions and Lyapunov exponents. We show that the new measure has linear dependence on the effective dimension of the attractor and it measures the variations in the sum of the Lyapunov spectrum. To illustrate the practical usefulness of the method, we employ it to identify various types of dynamical transitions in different nonlinear models. Also, we present testbed examples for the new method's robustness against the presence of noise and missing values in the time series. Furthermore, we use this method to analyze time series from the field of social dynamics, where we present an analysis of the US crime record's time series from the year 1975 to 1993. Using this method, we have found that dynamical complexity in robberies was influenced by the unemployment rate till late 1980's. We have also observed a dynamical transition in homicide and robbery rates in the late 1980's and early 1990's, leading to increase in the dynamical complexity of these rates.

preprint2013arXiv

Percolation-induced exponential scaling in the large current tails of random resistor networks

There is a renewed surge in percolation-induced transport properties of diverse nano-particle composites (cf. RSC Nanoscience & Nanotechnology Series, Paul O'Brien Editor-in-Chief). We note in particular a broad interest in nano-composites exhibiting sharp electrical property gains at and above percolation threshold, which motivated us to revisit the classical setting of percolation in random resistor networks but from a multiscale perspective. For each realization of random resistor networks above threshold, we use network graph representations and associated algorithms to identify and restrict to the percolating component, thereby preconditioning the network both in size and accuracy by filtering {\it a priori} zero current-carrying bonds. We then simulate many realizations per bond density and analyze scaling behavior of the complete current distribution supported on the percolating component. We first confirm the celebrated power-law distribution of small currents at the percolation threshold, and second we confirm results on scaling of the maximum current in the network that is associated with the backbone of the percolating cluster. These properties are then placed in context with global features of the current distribution, and in particular the dominant role of the large current tail that is most relevant for material science applications. We identify a robust, exponential large current tail that: 1. persists above threshold; 2. expands broadly over and dominates the current distribution at the expense of the vanishing power law scaling in the small current tail; and 3. by taking second moments, reproduces the experimentally observed power law scaling of bulk conductivity above threshold.

preprint2013arXiv

Resolving structural variability in network models and the brain

Large-scale white matter pathways crisscrossing the cortex create a complex pattern of connectivity that underlies human cognitive function. Generative mechanisms for this architecture have been difficult to identify in part because little is known about mechanistic drivers of structured networks. Here we contrast network properties derived from diffusion spectrum imaging data of the human brain with 13 synthetic network models chosen to probe the roles of physical network embedding and temporal network growth. We characterize both the empirical and synthetic networks using familiar diagnostics presented in statistical form, as scatter plots and distributions, to reveal the full range of variability of each measure across scales in the network. We focus on the degree distribution, degree assortativity, hierarchy, topological Rentian scaling, and topological fractal scaling---in addition to several summary statistics, including the mean clustering coefficient, shortest path length, and network diameter. The models are investigated in a progressive, branching sequence, aimed at capturing different elements thought to be important in the brain, and range from simple random and regular networks, to models that incorporate specific growth rules and constraints. We find that synthetic models that constrain the network nodes to be embedded in anatomical brain regions tend to produce distributions that are similar to those extracted from the brain. We also find that network models hardcoded to display one network property do not in general also display a second, suggesting that multiple neurobiological mechanisms might be at play in the development of human brain network architecture. Together, the network models that we develop and employ provide a potentially useful starting point for the statistical inference of brain network structure from neuroimaging data.

preprint2013arXiv

Robust Detection of Dynamic Community Structure in Networks

We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations (`optimization variance') and over randomizations of network structure (`randomization variance'). Because the modularity quality function typically has a large number of nearly-degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.

preprint2013arXiv

Role of social environment and social clustering in spread of opinions in co-evolving networks

Taking a pragmatic approach to the processes involved in the phenomena of collective opinion formation, we investigate two specific modifications to the co-evolving network voter model of opinion formation, studied by Holme and Newman [1]. First, we replace the rewiring probability parameter by a distribution of probability of accepting or rejecting opinions between individuals, accounting for the asymmetric influences in relationships among individuals in a social group. Second, we modify the rewiring step by a path-length-based preference for rewiring that reinforces local clustering. We have investigated the influences of these modifications on the outcomes of the simulations of this model. We found that varying the shape of the distribution of probability of accepting or rejecting opinions can lead to the emergence of two qualitatively distinct final states, one having several isolated connected components each in internal consensus leading to the existence of diverse set of opinions and the other having one single dominant connected component with each node within it having the same opinion. Furthermore, and more importantly, we found that the initial clustering in network can also induce similar transitions. Our investigation also brings forward that these transitions are governed by a weak and complex dependence on system size. We found that the networks in the final states of the model have rich structural properties including the small world property for some parameter regimes. [1] P. Holme and M. Newman, Phys. Rev. E 74, 056108 (2006).

preprint2013arXiv

Task-Based Core-Periphery Organisation of Human Brain Dynamics

As a person learns a new skill, distinct synapses, brain regions, and circuits are engaged and change over time. In this paper, we develop methods to examine patterns of correlated activity across a large set of brain regions. Our goal is to identify properties that enable robust learning of a motor skill. We measure brain activity during motor sequencing and characterize network properties based on coherent activity between brain regions. Using recently developed algorithms to detect time-evolving communities, we find that the complex reconfiguration patterns of the brain's putative functional modules that control learning can be described parsimoniously by the combined presence of a relatively stiff temporal core that is composed primarily of sensorimotor and visual regions whose connectivity changes little in time and a flexible temporal periphery that is composed primarily of multimodal association regions whose connectivity changes frequently. The separation between temporal core and periphery changes over the course of training and, importantly, is a good predictor of individual differences in learning success. The core of dynamically stiff regions exhibits dense connectivity, which is consistent with notions of core-periphery organization established previously in social networks. Our results demonstrate that core-periphery organization provides an insightful way to understand how putative functional modules are linked. This, in turn, enables the prediction of fundamental human capacities, including the production of complex goal-directed behavior.

preprint2012arXiv

Accuracy of Mean-Field Theory for Dynamics on Real-World Networks

Mean-field analysis is an important tool for understanding dynamics on complex networks. However, surprisingly little attention has been paid to the question of whether mean-field predictions are accurate, and this is particularly true for real-world networks with clustering and modular structure. In this paper, we compare mean-field predictions to numerical simulation results for dynamical processes running on 21 real-world networks and demonstrate that the accuracy of the theory depends not only on the mean degree of the networks but also on the mean first-neighbor degree. We show that mean-field theory can give (unexpectedly) accurate results for certain dynamics on disassortative real-world networks even when the mean degree is as low as 4.

preprint2012arXiv

Dynamic Network Centrality Summarizes Learning in the Human Brain

We study functional activity in the human brain using functional Magnetic Resonance Imaging and recently developed tools from network science. The data arise from the performance of a simple behavioural motor learning task. Unsupervised clustering of subjects with respect to similarity of network activity measured over three days of practice produces significant evidence of `learning', in the sense that subjects typically move between clusters (of subjects whose dynamics are similar) as time progresses. However, the high dimensionality and time-dependent nature of the data makes it difficult to explain which brain regions are driving this distinction. Using network centrality measures that respect the arrow of time, we express the data in an extremely compact form that characterizes the aggregate activity of each brain region in each experiment using a single coefficient, while reproducing information about learning that was discovered using the full data set. This compact summary allows key brain regions contributing to centrality to be visualized and interpreted. We thereby provide a proof of principle for the use of recently proposed dynamic centrality measures on temporal network data in neuroscience.

preprint2012arXiv

Taxonomies of Networks

The study of networks has grown into a substantial interdisciplinary endeavour that encompasses myriad disciplines in the natural, social, and information sciences. Here we introduce a framework for constructing taxonomies of networks based on their structural similarities. These networks can arise from any of numerous sources: they can be empirical or synthetic, they can arise from multiple realizations of a single process, empirical or synthetic, or they can represent entirely different systems in different disciplines. Since the mesoscopic properties of networks are hypothesized to be important for network function, we base our comparisons on summaries of network community structures. While we use a specific method for uncovering network communities, much of the introduced framework is independent of that choice. After introducing the framework, we apply it to construct a taxonomy for 746 individual networks and demonstrate that our approach usefully identifies similar networks. We also construct taxonomies within individual categories of networks, and in each case we expose non-trivial structure. For example we create taxonomies for similarity networks constructed from both political voting data and financial data. We also construct network taxonomies to compare the social structures of 100 Facebook networks and the growth structures produced by different types of fungi.

preprint2011arXiv

Dynamic reconfiguration of human brain networks during learning

Human learning is a complex phenomenon requiring flexibility to adapt existing brain function and precision in selecting new neurophysiological activities to drive desired behavior. These two attributes -- flexibility and selection -- must operate over multiple temporal scales as performance of a skill changes from being slow and challenging to being fast and automatic. Such selective adaptability is naturally provided by modular structure, which plays a critical role in evolution, development, and optimal network function. Using functional connectivity measurements of brain activity acquired from initial training through mastery of a simple motor skill, we explore the role of modularity in human learning by identifying dynamic changes of modular organization spanning multiple temporal scales. Our results indicate that flexibility, which we measure by the allegiance of nodes to modules, in one experimental session predicts the relative amount of learning in a future session. We also develop a general statistical framework for the identification of modular architectures in evolving systems, which is broadly applicable to disciplines where network adaptability is crucial to the understanding of system performance.

preprint2011arXiv

Party Polarization in Congress: A Network Science Approach

We measure polarization in the United States Congress using the network science concept of modularity. Modularity provides a conceptually-clear measure of polarization that reveals both the number of relevant groups and the strength of inter-group divisions without making restrictive assumptions about the structure of the party system or the shape of legislator utilities. We show that party influence on Congressional blocs varies widely throughout history, and that existing measures underestimate polarization in periods with weak party structures. We demonstrate that modularity is a significant predictor of changes in majority party and that turnover is more prevalent at medium levels of modularity. We show that two variables related to modularity, called `divisiveness' and `solidarity,' are significant predictors of reelection success for individual House members. Our results suggest that modularity can serve as an early warning of changing group dynamics, which are reflected only later by changes in party labels.

preprint2011arXiv

Social Structure of Facebook Networks

We study the social structure of Facebook "friendship" networks at one hundred American colleges and universities at a single point in time, and we examine the roles of user attributes - gender, class year, major, high school, and residence - at these institutions. We investigate the influence of common attributes at the dyad level in terms of assortativity coefficients and regression models. We then examine larger-scale groupings by detecting communities algorithmically and comparing them to network partitions based on the user characteristics. We thereby compare the relative importances of different characteristics at different institutions, finding for example that common high school is more important to the social organization of large institutions and that the importance of common major varies significantly between institutions. Our calculations illustrate how microscopic and macroscopic perspectives give complementary insights on the social organization at universities and suggest future studies to investigate such phenomena further.

preprint2010arXiv

Community Structure in the United Nations General Assembly

We study the community structure of networks representing voting on resolutions in the United Nations General Assembly. We construct networks from the voting records of the separate annual sessions between 1946 and 2008 in three different ways: (1) by considering voting similarities as weighted unipartite networks; (2) by considering voting similarities as weighted, signed unipartite networks; and (3) by examining signed bipartite networks in which countries are connected to resolutions. For each formulation, we detect communities by optimizing network modularity using an appropriate null model. We compare and contrast the results that we obtain for these three different network representations. In so doing, we illustrate the need to consider multiple resolution parameters and explore the effectiveness of each network representation for identifying voting groups amidst the large amount of agreement typical in General Assembly votes.

preprint2010arXiv

Community Structure in Time-Dependent, Multiscale, and Multiplex Networks

Network science is an interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. A prominent problem in network science is the algorithmic detection of tightly-connected groups of nodes known as communities. We developed a generalized framework of network quality functions that allowed us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through links that connect each node in one network slice to itself in other slices. This framework allows one to study community structure in a very general setting encompassing networks that evolve over time, have multiple types of links (multiplexity), and have multiple scales.

preprint2010arXiv

Comparing Community Structure to Characteristics in Online Collegiate Social Networks

We study the structure of social networks of students by examining the graphs of Facebook "friendships" at five American universities at a single point in time. We investigate each single-institution network's community structure and employ graphical and quantitative tools, including standardized pair-counting methods, to measure the correlations between the network communities and a set of self-identified user characteristics (residence, class year, major, and high school). We review the basic properties and statistics of the pair-counting indices employed and recall, in simplified notation, a useful analytical formula for the z-score of the Rand coefficient. Our study illustrates how to examine different instances of social networks constructed in similar environments, emphasizes the array of social forces that combine to form "communities," and leads to comparative observations about online social lives that can be used to infer comparisons about offline social structures. In our illustration of this methodology, we calculate the relative contributions of different characteristics to the community structure of individual universities and subsequently compare these relative contributions at different universities, measuring for example the importance of common high school affiliation to large state universities and the varying degrees of influence common major can have on the social structure at different universities. The heterogeneity of communities that we observe indicates that these networks typically have multiple organizing factors rather than a single dominant one.

preprint2010arXiv

Dynamical Clustering of Exchange Rates

We use techniques from network science to study correlations in the foreign exchange (FX) market over the period 1991--2008. We consider an FX market network in which each node represents an exchange rate and each weighted edge represents a time-dependent correlation between the rates. To provide insights into the clustering of the exchange rate time series, we investigate dynamic communities in the network. We show that there is a relationship between an exchange rate's functional role within the market and its position within its community and use a node-centric community analysis to track the time dynamics of this role. This reveals which exchange rates dominate the market at particular times and also identifies exchange rates that experienced significant changes in market role. We also use the community dynamics to uncover major structural changes that occurred in the FX market. Our techniques are general and will be similarly useful for investigating correlations in other markets.

preprint2010arXiv

The unreasonable effectiveness of tree-based theory for networks with clustering

We demonstrate that a tree-based theory for various dynamical processes yields extremely accurate results for several networks with high levels of clustering. We find that such a theory works well as long as the mean intervertex distance $\ell$ is sufficiently small - i.e., as long as it is close to the value of $\ell$ in a random network with negligible clustering and the same degree-degree correlations. We confirm this hypothesis numerically using real-world networks from various domains and on several classes of synthetic clustered networks. We present analytical calculations that further support our claim that tree-based theories can be accurate for clustered networks provided that the networks are "sufficiently small" worlds.

preprint2009arXiv

Communities in Networks

We survey some of the concepts, methods, and applications of community detection, which has become an increasingly important area of network science. To help ease newcomers into the field, we provide a guide to available methodology and open problems, and discuss why scientists from diverse backgrounds are interested in these problems. As a running theme, we emphasize the connections of community detection to problems in statistical physics and computational optimization.

preprint2009arXiv

Mutually-Antagonistic Interactions in Baseball Networks

We formulate the head-to-head matchups between Major League Baseball pitchers and batters from 1954 to 2008 as a bipartite network of mutually-antagonistic interactions. We consider both the full network and single-season networks, which exhibit interesting structural changes over time. We find interesting structure in the network and examine their sensitivity to baseball's rule changes. We then study a biased random walk on the matchup networks as a simple and transparent way to compare the performance of players who competed under different conditions and to include information about which particular players a given player has faced. We find that a player's position in the network does not correlate with his success in the random walker ranking but instead has a substantial effect on its sensitivity to changes in his own aggregate performance.

preprint2006arXiv

Random Walker Ranking for NCAA Division I-A Football

Each December, college football fans and pundits across America debate which two teams should meet in the NCAA Division I-A National Championship game. The Bowl Championship Series (BCS) standings employed to select the teams invited to this game are intended to provide an unequivocal #1 v. #2 game for the championship; however, this selection process has itself been highly controversial in recent years. The computer algorithms that constitute one part of the BCS standings often act as lightning rods for the controversy, in part because they are inadequately explained to the public. We present an alternative algorithm that is simply explained yet remains effective at ranking the best teams. We define a ranking in terms of biased random walkers on the graph formed by the schedule of games played, with two teams (vertices) connected by an edge if they played each other. Each random walker moves from team to team by selecting a game and "voting" for its winner with probability p, tracing out a never-ending path motivated by the "my team beat your team" argument. We study the statistical properties of a collection of such walkers, relate the rankings to the community structure of the underlying network, and demonstrate the results for recent NCAA Division I-A seasons. We also discuss the algorithm's asymptotic behavior, illustrated with some analytically tractable cases for round-robin tournaments, and discuss possible generalizations.