Networks

Structure and Dynamics of Brain Networks

Cohesive structures have long been thought to play an important role in information processing in the human brain. At the small scale of individual neurons, temporally coherent activity supports information transfer between cells. At a much larger scale, simultaneously active cortical areas form functional systems that enable behavior. However, the question of precisely what type of cohesive organization is present between the constituents of brain systems is steeped in controversy.  Moreover, although interactions between pairs of brain regions are easy to measure, the analysis of dynamic interactions across the whole human brain remained challenging until recent applications of network theory to neuroimaging data [1,2]. These efforts have led to enormous insights, including the establishments of links between the configuration of functional brain network and intelligence, links between altered brain network organization and disease, and more.

We employ techniques from subjects like network theory, dynamical systems, time-series analysis, and scientific computation to study similarity networks constructed from functional measurements of brain activity. This includes computation of basic network diagnostics and also state-of-the-art methods for algorithmic clustering (e.g., "community detection") in time-dependent networks [3], which we have generalized further through our studies of functional brain networks [2,4,5]. This includes development of new "null models" for community detection [5] and of methods to detect core-periphery organization [4,6] in networks.

We have demonstrated via analysis of networks constructed from functional Magnetic Resonance Imaging (fMRI) that there is a causal connection between brain-region "flexibility", as measured through changing community allegiance in time, and a subject's short-term learning of simple motor tasks (using a simplistic notion of "learning" that amounts to improved speed in task performance) [2].  We have also demonstrated the development of strategies for "chunking" data during such learning [7]. More recently, we have elucidated which brain regions are part of a stiff "core" of nodes and which are part of a flexibility "periphery", where we have found a beautiful correspondence between structural and dynamic notions of core-periphery organization [6].

Thus far, our research on networks in neuroscience has focused on motor learning in functional brain networks using a specific mode of data collection (namely, task-based fMRI). We are working with several research groups using data from several different modes, which have varying spatial and temporal resolutions and hence affect (in fundamental ways) both the properties of the resulting time series and of what scientific questions can be asked in the first place. For example, we expect that we can use time-dependent clustering techniques to elucidate temporal changes in brain networks in various situations, such as the effects of various drugs on schizophrenia patients or the recovery of damaged brains. In addition to interest neuroscience-oriented questions --- such as analysis of network changes in neuronal ensembles due to learning and development in Xenopus (a type of frog) --- this will entail further development of our tools for network analysis and time-series analysis. Additionally, although we have concentrated thus far on functional brain networks, we also wish to investigate structure and dynamics in physical networks of neurons.

For more information please contact Mason Porter, Sang Hoon Lee, Paul Broderson, or Puck Rombach.


Key References in this area

  1. E. Bullmore & O. Sporns, Nat Rev Neurosci 10, 186-198 (2009).
  2. D. S. Bassett, et al., Proc Natl Acad Sci USA 108, 7641-7646 (2011).
  3. P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, & J.-P. Onnela, Science 328, 876-878 (2010).
  4. D. S. Bassett, et al., arXiv:1210.3555 (2012).
  5. D. S. Bassett, et al., arXiv:1206.4358 (2012)
  6. M. P. Rombach, M. A. Porter, J. H. Fowler, & P. J. Mucha, arXiv:1202.2684 (2012).
  7. N. F. Wymbs, et al., Neuron 74, 936-946 (2012).

 


Consumer behaviour

Understanding consumer behaviour is important for a wide range of applications, from developing more successful marketing strategies to economic policy design. The aim of this project is to extract and understand the patterns that are present in shopping data. The data takes the form of a transaction history for each consumer, where we know when and how much they bought of a particular product, and have additional information on the demographics and products themselves. The industrial partner for this project is Unilever Ltd.

The underlying structure of the data can be conveniently represented as a temporal, weighted, bipartite network, where consumers and products form the two classes of nodes and links are given by the transactions. One can then use community detection to extract mesoscopic structure, yielding groups of products and consumers that are more densely connected, than would be expected if consumers bought products at random. The algorithm used to find these clusters is based on optimising a generalised version of the popular modularity quality function that allows for time-dependence and different types of edges. One of the challenges of finding meaningful communities in shopping data is the high level of behavioural noise. As modularity maximisation is a NP-hard problem, one has to apply heuristic methods that will usually only find local maxima. We have been able to obtain more robust results by using consensus clustering to combine the information from multiple runs of a stochastic heuristic.

The two datasets we have available are the purchase history of a swiss online supermarket, provided by Unilever, and the purchase history as well as detailed demographic and spatial information for a selection of customers of a number of supermarkets in the midwestern United States, provided by Brian Uzzi of Kellogg School of Management, Northwestern University. Thus far, we have been able to establish significant clustering in both datasets. For the swiss online supermarket, demographic factors appear to have at most a weak impact on the clusters found and limited usable product information makes interpretation difficult. Preliminary results for the US data indicate that brand loyalty is a potential source of clustering, at least in some product categories.

In the future, we plan to use the data to understand urban versus suburban shopping patterns, which should yield actionable insights that can be used by Unilever, as well as interesting sociological results. We are also interested to further develop methods to detect overlapping communities in noisy and temporal data. 

For more information please contact Lucas Jeub or Mason Porter.

Key references in this area

  • Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010). Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980): 876-878.
  • Porter, M. A., Onnela, J.-P., & Mucha, P. J. (2009). Communities in Networks. Notices of the AMS 56(9): 1082-1166.

 

    Network-based studies of infectious disease 

    Infectious diseases are the second largest cause of death worldwide, accounting for 23% of all deaths. Mathematical studies are commonly used by both researchers and public health officials to better understand disease spread and predict and counteract epidemics. The traditional ways to model infectious diseases use differential equations, such as the SIR and force-of-infection models. More recently, scientists have attempted network-based approaches, such as describing disease as a dynamical process on a network of contacts. In this project, we investigate the applicability of a novel network science methodology, using community detection on time-dependent correlation networks to model the geographical spread of disease.

    Using proprietary data on country-wide dengue fever, rubella, and H1N1 influenza occurrences for several years, we create networks with the provinces as nodes and correlation between the number of disease cases in each pair of provinces giving weights to the links between nodes. To study these temporally evolving networks, we use the framework of "multislice networks", which allows modelling the temporal aspect of the data with less data aggregation than with collections of ordinary (static) networks. We perform community detection, looking for groups of provinces in which disease patterns change in similar ways, and we analyse the properties of the communities over time. We also study the relations between epidemic spread and changes in different network and node statistics, to seek potential preepidemic signals.

    Preliminary results (performed on static networks) suggest that there may be a drop in modularity around the epidemic start time, as well as changes in node statistics such as participation coefficient and geodesic betweenness.

    We are currently investigating the statistical significance of the preliminary results by comparing their values to values observed in a random rewiring null model. We are looking at extending the definitions of the interesting statistics to multislice networks. We are also planning on changing the model to include time through using directed links and possibly a delay in the network creation.

    For more information please contact Marta Sarzynska or Mason Porter.

     

    Financial Networks

    The turmoil witnessed in financial markets in recent years has illustrated important links between seemingly disparate markets and a high level of connectivity of the global financial system. These interdependencies between financial institutions or assets are often poorly understood and can have large and unforeseen consequences, proving to be very important in providing insight into macro-economic risk and large corporate risk.

    Networks are used to represent complex systems of interacting entities. We are interested in investigating the structure and dynamics of financial networks (using data from HSBC). "Community detection" is an important tool in network analysis; it is used to cluster the data into densely connected groups and can reveal underlying structure in the network and detect functionalities or relationships between the nodes. In particular, we have been using new methods of network science developed specifically for community detection in time-dependent networks.

    Some challenges that arise in extracting communities from financial data include choosing an appropriate network representation (choice of the nodes and edges in the network), applying the method to the chosen network model and interpreting the output of the method. Another issue is also that of allowing overlap between the different communities, for which no method has been developed for time-dependent networks, and which is still unresolved at the level of static networks.

    To attempt to address some of these difficulties, we have been re-thinking some of the ideas in community detection for evolving networks, carrying out numerical experiments to attempt to extract robust community partitions and formulating null models to test the significance of the resulting partition.

    Up to this point, we have been studying a dataset of financial assets from different markets using a signed, weighted, fully connected time-dependent correlation network. Although we have been able to extract communities that seem to be consistent with previous studies  carried out on the same dataset and identify some important financial events across time, it seems that some of the features defined in the current community detection method need to be modified to account for signed edges. 

    The industrial partner for this project is HSBC.

    For more information please contact Marya Bazzi or Mason Porter.

    Key references in this area

    • P. J. Mucha, T. Richardson, K. Macon, M. Porter, J-P. Onnela (2010). Community Structure in Time Dependent, Multiscale, and Multiplex Networks. Science 328(5980): 876-878.
    • M. A. Porter, J-P. Onnela, P. J. Mucha. (2009). Communities in Networks. Notices of the American Mathematical Society 56(9) :1082-1097 & 1164-1166.
    • D. J. Fenn, M. A. Porter, S. Williams, M. McDonald, N. F. Johnson, N. S. Jones (2011). Temporal Evolution of Financial Market Correlations. Physical Review E 84(2): 026109.
    • D. J. Fenn, M. A. Porter, S. Williams, M. McDonald, N. F. Johnson, N. S. Jones (2009). Dynamic Communities in MultiChannel Data: An Application to the Foreign Exchange Market During the 2007-2008 Credit Crisis. Chaos 19(3): 033119.

     

    Network Navigability in Spatially Embedded Networks

    The last two decades of research on networks has witnessed a wealth of work focusing on their structural and dynamical properties from a global perspective, but little work has focused on the users of networks.  In the present era of smartphones equipped with global positioning systems, people have access to local information and finding efficient local pathways on networks (rather than just globally optimal ones) has become an ever more important problem to consider.  One might want to reach a given destination in a city, and the best path to follow requires one to consider a combination of geographical constraints, the structure of transportation networks, and traffic conditions that vary over multiple time scales.

    It is desirable to investigate realistic navigation behavior, and one way to start doing this is by adapting and generalizing algorithms from other situations.  For example, a greedy strategy can be used as a probe to explore spatial networks by using directional information for each move and without becoming trapped in a dead end.  One can use this approach to develop object functions that encode navigational information in the coordinates of edges (e.g. roads) and nodes (e.g. street intersections). It is also important to incorporate structural constraints that result from a network being embedded in space (e.g. a road network can be modeled as existing in a plane) and to consider stochastic edge weights that can result from variable traffic conditions.  One must thus incorporate ideas from both spatial and temporal networks in the design of navigation strategies.

    Our results demonstrate that measures of node and edge importance, which are called "centralities", need to be modified to incorporate navigation behavior, and we showed using road networks from 100 cities that consideration of such navigation gives insight into structural properties of networks that were not captured by previously existing measures.  Moreover, when using a greedy algorithm, it is paradoxically the case that removing some edges can sometimes enhance routing efficiency even though there are fewer travelling choices.  Importantly, we have also developed local routing algorithms that work effectively even in the presence of stcohastic edge weights, which must be considered in realistic traffic situations.

    In the future we will build on prior results by using network topology and geometry to improve routing algorithms.  This will entail not only employing new techniques the group has developed for investigating meso-scale structures like core-periphery structure and community structure but also generalizing these ideas for temporal networks.  For example, notions of core-periphery structure based around the idea of being on a lot of short cycles should be particular relevant to transport and navigational properties of networks.  We have begun to investigate these ideas using not only road networks but also biological transportation networks (fungal networks from numerous species and grown according to various protocols) using guidance from a methodology to classify networked systems by investigating mesoscopic modular structures.
     
    For more information please contact Sang Hoon Lee or Mason Porter.

    Key references in this area  

    • S.H. Lee and P. Holme (2011). Physica A 390: 3996.
    • S.H. Lee and P. Holme (2012). Phys. Rev. Lett. 108: 128701.
    • S.H. Lee and P. Holme. e-print arXiv:1205.0537.
    • S.H. Lee and P. Holme. e-print arXiv:1206.6651.
    • T. Hoffmann, R. Lambiotte, and M.A. Porter, e-print arXiv:1209.3504.
    • J.P. Onnela, D.J. Fenn, S. Reid, M.A. Porter, P.J. Mucha, M.D. Fricker, and N.S. Jones (2012). Phys. Rev. E 86: 036104.