TY - GEN
T1 - Local detection of critical nodes in active graphs
AU - Ozkaya, M. Yusuf
AU - Sanyuce, Ahmet Erdem
AU - Pinar, Ali
AU - Catalyurek, Umit V.
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/10/24
Y1 - 2018/10/24
N2 - The identification of critical nodes in a graph is a fundamental task in network analysis. Centrality measures are commonly used for this purpose. These methods rely on two assumptions that restrict their applicability. First, they only depend on the topology of the network and do not consider the activity over the network. Second, they assume the entire network is available. However, in many applications, it is the underlying activity of the network such as interactions and communications that makes a node critical, and it is hard to collect the entire network topology, when the network is vast and autonomous. We propose a new measure, Active Betweenness Cardinality, where the importance of the nodes are based not on the static structure, but the active utilization of the network. We show how this metric can be computed efficiently by only local information for a given node and how we can locate the critical nodes by using only a few nodes. We also show how this metric can be used to monitor a network and identify node failures. We evaluate our metric and algorithms on real-world networks and show the effectiveness of the proposed methods.
AB - The identification of critical nodes in a graph is a fundamental task in network analysis. Centrality measures are commonly used for this purpose. These methods rely on two assumptions that restrict their applicability. First, they only depend on the topology of the network and do not consider the activity over the network. Second, they assume the entire network is available. However, in many applications, it is the underlying activity of the network such as interactions and communications that makes a node critical, and it is hard to collect the entire network topology, when the network is vast and autonomous. We propose a new measure, Active Betweenness Cardinality, where the importance of the nodes are based not on the static structure, but the active utilization of the network. We show how this metric can be computed efficiently by only local information for a given node and how we can locate the critical nodes by using only a few nodes. We also show how this metric can be used to monitor a network and identify node failures. We evaluate our metric and algorithms on real-world networks and show the effectiveness of the proposed methods.
UR - https://www.scopus.com/pages/publications/85057320480
U2 - 10.1109/ASONAM.2018.8508323
DO - 10.1109/ASONAM.2018.8508323
M3 - Conference contribution
AN - SCOPUS:85057320480
T3 - Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
SP - 107
EP - 110
BT - Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
A2 - Tagarelli, Andrea
A2 - Reddy, Chandan
A2 - Brandes, Ulrik
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 10th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
Y2 - 28 August 2018 through 31 August 2018
ER -