TY - GEN
T1 - On the connectivity of multi-layered networks
T2 - 15th IEEE International Conference on Data Mining, ICDM 2015
AU - Chen, Chen
AU - He, Jingrui
AU - Bliss, Nadya
AU - Tong, Hanghang
PY - 2016/1/5
Y1 - 2016/1/5
N2 - Networks appear naturally in many high-impact real-world applications. In an increasingly connected and coupled world, the networks arising from many application domains are often collected from different channels, forming the so-called multi-layered networks, such as cyber-physical systems, organization-level collaboration platforms, critical infrastructure networks and many more. Compared with single-layered networks, multi-layered networks are more vulnerable as even a small disturbance on one supporting layer/network might cause a ripple effect to all the dependent layers, leading to a catastrophic/cascading failure of the entire system. The state-of-the-art has been largely focusing on modeling and manipulating the cascading effect of two-layered interdependent network systems for some specific type of network connectivity measure. This paper generalizes the challenge to multiple dimensions. First, we propose a new data model for multi-layered networks MULAN, which admits an arbitrary number of layers with a much more flexible dependency structure among different layers, beyond the current pair-wise dependency. Second, we unify a wide range of classic network connectivity measures SUBLINE. Third, we show that for any connectivity measure in the SUBLINE family, it enjoys the diminishing returns property which in turn lends itself to a family of provable near-optimal control algorithms with linear complexity. Finally, we conduct extensive empirical evaluations on real network data, to validate the effectiveness of the proposed algorithms.
AB - Networks appear naturally in many high-impact real-world applications. In an increasingly connected and coupled world, the networks arising from many application domains are often collected from different channels, forming the so-called multi-layered networks, such as cyber-physical systems, organization-level collaboration platforms, critical infrastructure networks and many more. Compared with single-layered networks, multi-layered networks are more vulnerable as even a small disturbance on one supporting layer/network might cause a ripple effect to all the dependent layers, leading to a catastrophic/cascading failure of the entire system. The state-of-the-art has been largely focusing on modeling and manipulating the cascading effect of two-layered interdependent network systems for some specific type of network connectivity measure. This paper generalizes the challenge to multiple dimensions. First, we propose a new data model for multi-layered networks MULAN, which admits an arbitrary number of layers with a much more flexible dependency structure among different layers, beyond the current pair-wise dependency. Second, we unify a wide range of classic network connectivity measures SUBLINE. Third, we show that for any connectivity measure in the SUBLINE family, it enjoys the diminishing returns property which in turn lends itself to a family of provable near-optimal control algorithms with linear complexity. Finally, we conduct extensive empirical evaluations on real network data, to validate the effectiveness of the proposed algorithms.
KW - Connectivity control
KW - Multi-layered networks
UR - http://www.scopus.com/inward/record.url?scp=84963617402&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84963617402&partnerID=8YFLogxK
U2 - 10.1109/ICDM.2015.104
DO - 10.1109/ICDM.2015.104
M3 - Conference contribution
AN - SCOPUS:84963617402
T3 - Proceedings - IEEE International Conference on Data Mining, ICDM
SP - 715
EP - 720
BT - Proceedings - 15th IEEE International Conference on Data Mining, ICDM 2015
A2 - Aggarwal, Charu
A2 - Zhou, Zhi-Hua
A2 - Tuzhilin, Alexander
A2 - Xiong, Hui
A2 - Wu, Xindong
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 14 November 2015 through 17 November 2015
ER -