Community Structure In Multislice Networks

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.

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.