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.