Multiplex networks

Authors:
Open Access
Publisher website
Google Scholar
Abstract
Real-world networks often consist of multiple layers, be they infrastructure such as airline networks or social such as collaboration networks. A common aspect to these networks is that there are multiple sub-networks that evolve in parallel on the same node set -- these are referred to as multiplex networks. For example, in the case of airline networks, the cities (nodes) have been well-established for several decades if not centuries, but over time new airlines (sub-networks) emerge and each airline creates its own flight linkages between cities. Similarly multiple modalities of communications evolve in parallel between individuals (nodes) such as E-mail, SMS, and Online Social Networks, e.g., Facebook and Twitter. While in some multiplex networks, each layer evolves independently from other layers over time, in other multiple networks, the evolution of a layer is coupled with that of other layers -- a process referred to as co-evolution. In this paper, we propose a novel generative model, BINBALL, for a class of multiplex networks whose structure may co-evolve (that is, depend on as well as influence) the structure of the individual networks. We validate our model using a multiplex data set for the European Air Transportation Network (EATN). We also investigate questions regarding the algorithmic complexity of finding short paths through multiplex networks as well as coverage of nodes using a minimum number of layers. We show that while certain problems in this space can be solved in polynomial time, others are NP hard. Among the latter, some problems are approximable, whereas others are not. Finally, we demonstrate that BINBALL is a good generative model since it is able to generate random networks whose degree as well as path length distributions closely match those of the EATN.
Funding Information
  • U.S. Army Research Laboratory (W911NF-09-2-0053)

This publication has 12 references indexed in Scilit: