Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2808797.2808900 | ASONAM |
Keywords | Field | DocType |
multiplex network,BINBALL model,algorithmic complexity,European air transportation network,EATN,NP-hard problem | Data mining,Social network,Computer science,Hierarchical network model,Complex network,Artificial intelligence,Time complexity,Distributed computing,Interdependent networks,Evolving networks,Multiplexing,Machine learning,Generative model | Conference |
Citations | PageRank | References |
4 | 0.49 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prithwish Basu | 1 | 703 | 52.93 |
| Ravi Sundaram | 2 | 762 | 72.13 |
| Matthew Dippel | 3 | 4 | 1.17 |