Community Structure In Multislice Networks
Lead Research Organisation:
University of Oxford
Department Name: Mathematical Institute
Abstract
Network science, the study of systems of interconnected entities and their functional interactions, has three principal goals:
1. Discover and enumerate the basic principles of networked systems.
2. Use structure, dynamics, and demographics to infer functional interactions when they are not directly prescribed.
3. Predict network structure and demographics, and use mathematical and computational methods to manipulate existing networks and design new networks with desired properties.
Networks provide a powerful tool for representing and analysing complex systems of interacting entities. They arise in the physical, biological, social, and information sciences and can be used to represent interactions between proteins, friendships between people, hyperlinks between web pages, and so on. A network consists of a set of entities (called "vertices") that are connected to each other by ties (called "edges").
Most studies of networks consider static networks with a single type of edge, and numerous tools have been developed to study such networks. However, networks that arise in applications are often more complicated. They can be "dynamic" in that they can have a time-dependent structure, which might represent changes in the committee assignments or voting patterns of politicians over time or different functional connectivity of brain regions during different parts of a motor activity. They can also be "multiplex" in that they include multiple edge types, such politicians who are connected both via common committee assignments and similar voting patterns.
Although researchers have long been aware that networks in applications are both dynamic and multiplex, it is only in the past few years that high-quality data has become available to study such situations effectively. I recently helped develop a "multislice" framework for networks, along with accompanying algorithmic tools, which can be used for studying time-dependent and multpliex networks (Mucha et al, Science, 2010).
The multislice framework departs from the norm in network science, as it formulates networks using three-dimensional arrays of numbers instead of the usual adjacency matrices (i.e., two-dimensional arrays). The 2010 paper developed a tool in multislice networks for the algorithmic detection of structures known as "communities", each of which consists of a set of vertices that are connected more densely to each other than they are to vertices in the rest of the network. The presence of different types of network edges, which are interrelated and evolve in time, raises conceptual and practical questions about network structure, and the multislice framework can be used to try to answer them.
The proof of principle in our 2010 paper paves the way to studying dynamic and multiplex networks in subjects such as biology and political science. However, applying this framework to applications in practice will require considerable effort on both conceptual and application-oriented fronts. The proposed programme will make major headway towards this goal, especially in the area of community structure. Through my collaborations (see Letters of Support), I have access to large data sets from political science and biology. Overcoming the challenging nature of dynamic and multiplex data will yield interesting insights both conceptually and for applications. Much is known about community structure in static networks with only a single type of edge, but almost nothing is understood about community structure in either dynamic or multiplex networks. Most networks encountered in applications have such features, and my proposal directly addresses this issue.
1. Discover and enumerate the basic principles of networked systems.
2. Use structure, dynamics, and demographics to infer functional interactions when they are not directly prescribed.
3. Predict network structure and demographics, and use mathematical and computational methods to manipulate existing networks and design new networks with desired properties.
Networks provide a powerful tool for representing and analysing complex systems of interacting entities. They arise in the physical, biological, social, and information sciences and can be used to represent interactions between proteins, friendships between people, hyperlinks between web pages, and so on. A network consists of a set of entities (called "vertices") that are connected to each other by ties (called "edges").
Most studies of networks consider static networks with a single type of edge, and numerous tools have been developed to study such networks. However, networks that arise in applications are often more complicated. They can be "dynamic" in that they can have a time-dependent structure, which might represent changes in the committee assignments or voting patterns of politicians over time or different functional connectivity of brain regions during different parts of a motor activity. They can also be "multiplex" in that they include multiple edge types, such politicians who are connected both via common committee assignments and similar voting patterns.
Although researchers have long been aware that networks in applications are both dynamic and multiplex, it is only in the past few years that high-quality data has become available to study such situations effectively. I recently helped develop a "multislice" framework for networks, along with accompanying algorithmic tools, which can be used for studying time-dependent and multpliex networks (Mucha et al, Science, 2010).
The multislice framework departs from the norm in network science, as it formulates networks using three-dimensional arrays of numbers instead of the usual adjacency matrices (i.e., two-dimensional arrays). The 2010 paper developed a tool in multislice networks for the algorithmic detection of structures known as "communities", each of which consists of a set of vertices that are connected more densely to each other than they are to vertices in the rest of the network. The presence of different types of network edges, which are interrelated and evolve in time, raises conceptual and practical questions about network structure, and the multislice framework can be used to try to answer them.
The proof of principle in our 2010 paper paves the way to studying dynamic and multiplex networks in subjects such as biology and political science. However, applying this framework to applications in practice will require considerable effort on both conceptual and application-oriented fronts. The proposed programme will make major headway towards this goal, especially in the area of community structure. Through my collaborations (see Letters of Support), I have access to large data sets from political science and biology. Overcoming the challenging nature of dynamic and multiplex data will yield interesting insights both conceptually and for applications. Much is known about community structure in static networks with only a single type of edge, but almost nothing is understood about community structure in either dynamic or multiplex networks. Most networks encountered in applications have such features, and my proposal directly addresses this issue.
Planned Impact
Huge advances in information technology during the last decade have yielded a wealth of data (from industry, academia, government, and the public sector) that can be analysed using the tools of network science. The data provided by my collaborators (see Letters of Support) is crucial for the proposed programme, and they have the potential to yield significant end user benefits. This includes biological insights in areas such as motor control by the brain and relationships between protein structure and function, which can help suggest laboratory experiments; and political insights on legislatures, which can help in the design of empirical and qualitative research by political scientists. One specific example in biology is finding cohesive clusters in fMRI data in experiments on motor control (as will be done in the proposed programme), which will allow the comparison of patients with healthy versus impaired motor skills and, in particular, of the different structures of the fMRI data that correlate strongly with each of them (and how the structure in the data changes as such impairment develops in time). Ultimately, it is hoped that this can help facilitate early detection of potential motor impairment and even the design of preventative measures. To give another example, understanding how complex political and social networks function is important for the government of society and for understanding of such processes and its checks and balances. Social networks are well known to play a crucial role in politics, but this is known at a ``black box" level rather than mechanistically, and finding cohesive clusters of individuals and organizations involved in politics through legislation and campaign finance can help make such informal structures and their checks and balances more transparent to those being governed.
People |
ORCID iD |
| Mason Porter (Principal Investigator) |
Publications
Hoffmann T
(2012)
Decentralized Routing on Spatial Networks with Stochastic Edge Weights
Bassett D
(2012)
Task-Based Core-Periphery Organisation of Human Brain Dynamics
Bassett D
(2012)
Robust Detection of Dynamic Community Structure in Networks
HARRINGTON H
(2013)
Commentary: Teach network science to teenagers
in Network Science
Mucha, Peter J.
(2013)
Task-Based Core-Periphery Organization of Human Brain Dynamics
Bassett DS
(2013)
Task-based core-periphery organization of human brain dynamics.
in PLoS computational biology
Hoffmann T
(2013)
Decentralized routing on spatial networks with stochastic edge weights.
in Physical review. E, Statistical, nonlinear, and soft matter physics
Bassett DS
(2013)
Robust detection of dynamic community structure in networks.
in Chaos (Woodbury, N.Y.)
Mantzaris A
(2013)
Dynamic network centrality summarizes learning in the human brain
in Journal of Complex Networks
Cozzo E
(2013)
Structure of Triadic Relations in Multiplex Networks
Harrington H
(2013)
Teach Network Science to Teenagers
Kivela M
(2013)
Multilayer Networks
in SSRN Electronic Journal
Mucha, Peter J.
(2013)
Robust detection of dynamic community structure in networks
Hu H
(2013)
A Method Based on Total Variation for Network Modularity Optimization Using the MBO Scheme
in SIAM Journal on Applied Mathematics
Kivelä M
(2013)
Multilayer Networks
De Domenico M
(2013)
Mathematical Formulation of Multilayer Networks
in Physical Review X
De Domenico M
(2013)
Mathematical Formulation of Multi-Layer Networks
Lee S
(2014)
Matchmaker, Matchmaker, Make Me a Match: Migration of Populations via Marriages in the Past
in Physical Review X
De Domenico M
(2014)
MuxViz: a tool for multilayer analysis and visualization of networks
in Journal of Complex Networks
Sarzynska M
(2014)
Null Models for Community Detection in Spatially-Embedded, Temporal Networks
Bassett DS
(2014)
Cross-linked structure of network evolution.
in Chaos (Woodbury, N.Y.)
Sarzynska M
(2014)
Null Models for Community Detection in Spatially-Embedded, Temporal Networks
Kivela M
(2014)
Multilayer networks
in Journal of Complex Networks
Lee SH
(2014)
Density-based and transport-based core-periphery structures in networks.
in Physical review. E, Statistical, nonlinear, and soft matter physics
Porter M
(2014)
Dynamical Systems on Networks: A Tutorial
De Domenico M
(2014)
MuxViz: A Tool for Multilayer Analysis and Visualization of Networks
Cozzo E
(2015)
Structure of triadic relations in multiplex networks
in New Journal of Physics
Taylor D
(2015)
Erratum: topological data analysis of contagion maps for examining spreading processes on networks.
in Nature communications
Jeub LG
(2015)
Think locally, act locally: detection of small, medium-sized, and large communities in large networks.
in Physical review. E, Statistical, nonlinear, and soft matter physics
Bassett D
(2015)
Extraction of force-chain network architecture in granular materials using community detection
in Soft Matter
Taylor D
(2015)
Topological data analysis of contagion maps for examining spreading processes on networks.
in Nature communications
Balachandran, Prakash
(2015)
Think locally, act locally: Detection of small, medium-sized, and large communities in large networks
Mischaikow, Konstantin
(2015)
Topological data analysis of contagion maps for examining spreading processes on networks
Porter M
(2016)
Dynamical Systems on Networks - A Tutorial
De Domenico M
(2016)
The physics of spreading processes in multilayer networks
Sarzynska M
(2016)
Null models for community detection in spatially embedded, temporal networks
in Journal of Complex Networks
Bazzi M
(2016)
Community Detection in Temporal Multilayer Networks, with an Application to Correlation Networks
in Multiscale Modeling & Simulation
De Domenico Manlio
(2016)
The physics of spreading processes in multilayer networks
in NATURE PHYSICS
Lee S
(2016)
Mesoscale analyses of fungal networks as an approach for quantifying phenotypic traits
in Journal of Complex Networks
Porter, Mason A.
(2016)
The physics of spreading processes in multilayer networks
| Description | We have conducted a study of long-term human migration that includes both "diffusive" and "convective" effects. Such considerations are important for investigations of ideas such as urbanization and cultural dissemination. For our study, we used family-book data from Korea as well as data from surnames in Czechoslovakia. We also have made progress on investigation of meso-scale network structures in both static and multilayer networks. We have significant new results on an application to fungal notes and in core-periphery structure. We have also made excellent progress on multilayer community structure in applications such as detection of Lagrangian coherent structures in fluid flow. We have also worked with data from politics and functional brain networks. Some papers are completed and several others are in progress. ---- I have noted that the 'Outcomes' part of the website does not include any easy medium to indicate papers that are in-press or which are on preprint servers but not yet accepted for publication. Accordingly, I list the following papers (which are also outcomes of this grant) here temporarily until they appear in final published form: Bassett, Danielle S.; Owens, Eli T.; Porter, Mason A.; Manning, M. Lisa; and Daniels, Karen E. [2014], Extraction of Force-Chain Network Architecture in Granular Materials Using Community Detection, arXiv:1408.3841. Lee, Sang Hoon; Fricker, Mark D.; and Porter, Mason A. [2014], Mesoscale Analyses of Fungal Networks, arXiv:1406.5855. Taylor, Dane; Klimm, Florian; Harrington, Heather A.; Kramár, Miroslav; Mischaikow, Konstantin; Porter, Mason A.; and Mucha, Peter J. [2014], Complex Contagions on Noisy Geometric Networks, arXiv:1408.1168. De Domenico, Manlio; Porter, Mason A.; and Arenas, Alex [2014], MuxViz: A Tool for Multilayer Analysis and Visualization of Networks, Journal of Complex Networks, advanced access, doi:10.1093/comnet/cnu038 (arXiv:1405.0843). We have also developed open-source software that goes with this. Jeub, Lucas G. S.; Balachandran, Prakash; Porter, Mason A.; Mucha, Peter J.; and Mahoney, Michael W. [2014], Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks, arXiv:1403.3795. We have also developed open-source software that goes with this. Sarzynska, Marta; Leicht, Elizabeth A.; Chowell, Gerardo; and Porter, Mason A. [2014], Null Models for Community Detection in Spatially-Embedded, Temporal Networks, submitted to Physical Review E, arXiv:1407.6297. Porter, Mason A.; and Gleeson, James P. [2014], Dynamical Systems on Networks: A Tutorial, arXiv1403.7663 Cozzo, Emanuele; Kivelä, Mikko; De Domenico, Manlio; Solé, Albert; Arenas, Alex; Gómez, Sergio; Porter, Mason A.; and Moreno, Yamir [2013], Clustering Coefficients in Multiplex Networks, arXiv:1307.6780. |
| Exploitation Route | Our generalization of methods to cluster data ("community detection", core-periphery detection, etc.) can be used for things like finding differences in the structure of brain networks in normal vs schizophrenic people (and also differences based on whether they are taking medication). This could hopefully eventually lead to clinical applications. Also, in financial systems, it could help improve early warning systems for crashes. When studying contagions, it could give early indications of possible epidemics in the hopes of preventing or at least ameliorating them through appropriate vaccination strategies. Indeed, our methods to cluster data has the potential to be used to give insights (including actionable ones) in myriad applications --- including not only political sciences, plant sciences, and neurscience (which we're pursuing) but also materials science, protein interactions, financial systems, biological contagions, and numerous other applications. For example, in financial systems, it could help improve early warning systems for crashes. When studying contagions, it could give early indications of possible epidemics in the hopes of preventing or at least ameliorating them through appropriate vaccination strategies. The calculations of centrality measures and notions of core-periphery structure in a rabbit-warren network successfully identified good locations for nests (matching very well with the opinions of a rabbit expert), and this might be useful in predictive situations where such information is not already known. One of the outputs is a review article on "multilayer networks" that is helping to drive forward the entire field. Ideally, it provides a grounding for the entire field that will help influence results from numerous scholars for many years to come. |
| Sectors | Communities and Social Services/Policy Creative Economy Digital/Communication/Information Technologies (including Software) Education Environment Financial Services and Management Consultancy Healthcare Culture Heritage Museums and Collections Security and Diplomacy Transport Other |
| Description | FET-Proactive Project, FP7-ICT-2011-8 |
| Amount | € 1,520,540 (EUR) |
| Funding ID | 317614 |
| Organisation | European Commission |
| Sector | Public |
| Country | Belgium |
| Start | 11/2012 |
| End | 10/2015 |
| Title | Code for visualization and local community detection in networks |
| Description | There are two groups of code. They go with the following paper: http://arxiv.org/abs/1403.3795 (accepted for publication in Physical Review E). One set of code is for local community detection in networks, and the other is for network visualization. There are two URLs: https://github.com/LJeub/SpringVisCom , https://github.com/LJeub/LocalCommunities |
| Type Of Technology | Software |
| Year Produced | 2014 |
| Open Source License? | Yes |
| Impact | None yet |
| URL | https://github.com/LJeub/LocalCommunities |
| Title | GenLouvain 2.0 |
| Description | GenLouvain 2.0 is a new version of the community-detection algorithm GenLouvain (the first public version of which dates to 2011). |
| Type Of Technology | Software |
| Year Produced | 2014 |
| Open Source License? | Yes |
| Impact | Various groups have been using versions of GenLouvain since 2011, and it has been used in various publications by a diverse group of authors. |
| URL | http://netwiki.amath.unc.edu/GenLouvain/GenLouvain |
| Title | MuxViz: Platform for Multilayer Analysis and Visualization |
| Description | MuxViz is software for the analysis and visualization of multilayer networks. It is open-source and expandable. It is described in the following paper: http://comnet.oxfordjournals.org/content/early/2014/10/12/comnet.cnu038.abstract |
| Type Of Technology | Software |
| Year Produced | 2014 |
| Open Source License? | Yes |
| Impact | None yet. |
| URL | http://muxviz.net |
| Description | Blog entry for Oxford University Press |
| Form Of Engagement Activity | A magazine, newsletter or online publication |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Public/other audiences |
| Results and Impact | More people looked at my review article on multilayer networks and at the journal in which it appeared. None of which I am aware |
| Year(s) Of Engagement Activity | |
| URL | http://blog.oup.com/2014/11/rumors-diseases-memes-networks/ |
| Description | Board of Experts, Complex Networks, Lake Como School of Advanced Studies |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | The first summer school will take place in 2015. None yet. |
| Year(s) Of Engagement Activity | |
| URL | http://ntma.lakecomoschool.org |
| Description | Invited participant in long-term academic program (ICERM, Brown University, network science and graph algorithms) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | I participated in a research program and interacted with other participants in the usual way (academic discussions and so on). I worked on a paper with existing collaborators who were also visiting, and we have now submitted our paper. |
| Year(s) Of Engagement Activity | |
| URL | http://icerm.brown.edu/sp-s14/ |
| Description | Member, Education Committee, Society for Industrial and Applied Mathematics |
| Form Of Engagement Activity | A formal working group, expert panel or dialogue |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | We discuss, give input on, and occasional enact decisions related to education and applied mathematics. We developed documents to try to influence big changes in applied mathematics curriculum. |
| Year(s) Of Engagement Activity | |
| Description | Member, Organizing Committee, semester program on Dynamics of Biologically Inspired Networks, Mathematical Biosciences Institute (MBI), Spring 2016 |
| Form Of Engagement Activity | A formal working group, expert panel or dialogue |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | The semester occurs in 2016 and work is ongoing. I am also the lead organizer of one of the workshops in the semester: http://mbi.osu.edu/event/?id=898 The semester occurs in 2016 and work is ongoing. |
| Year(s) Of Engagement Activity | |
| URL | http://mbi.osu.edu/programs/emphasis-programs/spring-2016-dynamics-biologically-inspired-networks/ |
| Description | Member, Subcommittee on Mathematics Across the Disciplines, Committee on the Undergraduate Program in Mathematics, Mathematical Association of America |
| Form Of Engagement Activity | A formal working group, expert panel or dialogue |
| Part Of Official Scheme? | Yes |
| Geographic Reach | National |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | We discussed education issues, produced documents, tried to influence people, etc. |
| Year(s) Of Engagement Activity | |
| Description | Organizer, 2014 AMS Mathematics Research Community on Network Science |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | The MRC established a community of researchers (including new collaborations and projects) of young network scientists, who continue to communicate with each other a great deal. |
| Year(s) Of Engagement Activity | |
| URL | http://www.ams.org/programs/research-communities/mrc-14 |
| Description | Outreach Program to Teach Network Science to School Students |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Schools |
| Results and Impact | Designed and organized mathematics workshops on Network Science for students in Years 9-11 (ages 13-16), with the primary focus on Year 9 (both in Somerville College in Oxford and in visits to schools throughout the UK) [2012-present]. Here is a video --- called "Sharing the Beauty of Networks" --- describing these activities (which EPSRC also posted on it website a while back): http://t.co/k2WEkHjsp1 My team and I developed teaching materials and published them in a peer-reviewed journal. The materials and the video above have circulated very widely. They have been used by many people internationally, and some of these people have also built on these materials further. This work has also led to my participation as part of a team to develop "Networks Literacy" curriculum to use in schools. (That curriculum has not yet been released.) |
| Year(s) Of Engagement Activity | 2012,2013,2014 |
| URL | http://t.co/k2WEkHjsp1 |
| Description | Program Committee, NetSci 2015 |
| Form Of Engagement Activity | A formal working group, expert panel or dialogue |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | The conference takes place in 2015, but that was not an option in the year field. None yet. |
| Year(s) Of Engagement Activity | |
| URL | http://netsci2015.net |
| Description | Senior Program Committee, 6th International Conference on Social Informatics (SocInfo 2014) |
| Form Of Engagement Activity | A formal working group, expert panel or dialogue |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | It will occur in a few days (as of this writing on 6/11/14). None yet |
| Year(s) Of Engagement Activity | |
| URL | http://socinfo2014.org |
| Description | Sharing presentation slides on slideshare |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | I reached numerous people with my slides beyond the specific venues where I gave my talks. They are available at the following URLs: http://www.slideshare.net/masonporter/multilayer-tutorialnetsci2014slightlyupdated , http://www.slideshare.net/masonporter/cascades-and-social-influence-on-networks-ucsb-3-oct-2014?related=1 None in particular aside from more people being aware of my presentations |
| Year(s) Of Engagement Activity | |
| URL | http://www.slideshare.net/masonporter/multilayer-tutorialnetsci2014slightlyupdated |
| Description | editorial boards of many journals |
| Form Of Engagement Activity | A formal working group, expert panel or dialogue |
| Part Of Official Scheme? | Yes |
| Geographic Reach | International |
| Primary Audience | Other academic audiences (collaborators, peers etc.) |
| Results and Impact | I have done the usual things that editors of journals do. This has impacted which papers get published in these journals. |
| Year(s) Of Engagement Activity | |