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
Bassett DS
(2015)
Extraction of force-chain network architecture in granular materials using community detection.
in Soft matter
Bassett DS
(2013)
Task-based core-periphery organization of human brain dynamics.
in PLoS computational biology
Bassett DS
(2013)
Robust detection of dynamic community structure in networks.
in Chaos (Woodbury, N.Y.)
Bassett DS
(2014)
Cross-linked structure of network evolution.
in Chaos (Woodbury, N.Y.)
Bazzi M
(2016)
Community Detection in Temporal Multilayer Networks, with an Application to Correlation Networks
in Multiscale Modeling & Simulation
Cozzo E
(2015)
Structure of triadic relations in multiplex networks
in New Journal of Physics
CUCURINGU M
(2016)
Detection of core-periphery structure in networks using spectral methods and geodesic paths
in European Journal of Applied Mathematics
De Domenico M
(2013)
Mathematical Formulation of Multilayer Networks
in Physical Review X
De Domenico Manlio
(2016)
The physics of spreading processes in multilayer networks
in NATURE PHYSICS
HARRINGTON H
(2013)
Commentary: Teach network science to teenagers
in Network Science
Hoffmann T
(2013)
Decentralized routing on spatial networks with stochastic edge weights.
in Physical review. E, Statistical, nonlinear, and soft matter physics
Hoffmann T
(2012)
Decentralized Routing on Spatial Networks with Stochastic Edge Weights
Hu H
(2013)
A Method Based on Total Variation for Network Modularity Optimization Using the MBO Scheme
in SIAM Journal on Applied Mathematics
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
Kivela M
(2014)
Multilayer networks
in Journal of Complex Networks
Lee S
(2016)
Mesoscale analyses of fungal networks as an approach for quantifying phenotypic traits
in Journal of Complex Networks
Lee S
(2014)
Matchmaker, Matchmaker, Make Me a Match: Migration of Populations via Marriages in the Past
in Physical Review X
Lee Sang Hoon
(2015)
Time-dependent community structure in legislation cosponsorship networks in the Congress of the Republic of Peru
in arXiv e-prints
Lee Sang Hoon
(2014)
Mesoscale analyses of fungal networks as an approach for quantifying phenotypic traits
in arXiv e-prints
Lee SH
(2014)
Density-based and transport-based core-periphery structures in networks.
in Physical review. E, Statistical, nonlinear, and soft matter physics
Mantzaris A
(2013)
Dynamic network centrality summarizes learning in the human brain
in Journal of Complex Networks
Taylor D
(2017)
Eigenvector-Based Centrality Measures for Temporal Networks
in Multiscale Modeling & Simulation
Taylor D
(2015)
Topological data analysis of contagion maps for examining spreading processes on networks.
in Nature communications
Description | FET-Proactive Project, FP7-ICT-2011-8 |
Amount | € 1,520,540 (EUR) |
Funding ID | 317614 |
Organisation | European Commission |
Sector | Public |
Country | European Union (EU) |
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 |