Incremental deployment of network monitors based on Group Betweenness Centrality

DOI10.1016/J.IPL.2009.07.019zbMATH Open1209.68364arXiv0904.0352OpenAlexW2055438560MaRDI QIDQ990953FDOQ990953

Yuval Elovici, Rami Puzis, Polina Zilberman, Shlomi Dolev

Publication date: 1 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: In many applications we are required to increase the deployment of a distributed monitoring system on an evolving network. In this paper we present a new method for finding candidate locations for additional deployment in the network. This method is based on the Group Betweenness Centrality (GBC) measure that is used to estimate the influence of a group of nodes over the information flow in the network. The new method assists in finding the location of k additional monitors in the evolving network, such that the portion of additional traffic covered is at least (1-1/e) of the optimal.

Full work available at URL: https://arxiv.org/abs/0904.0352

Recommendations

• scientific article; zbMATH DE number 5663542
• Traffic monitor deployment in IP networks
• Routing betweenness centrality
• scientific article; zbMATH DE number 5024629
• Monitoring the topology of growing dynamical networks

zbMATH Keywords

graph algorithmsdistributed systemsinterconnection networksnetwork centralitygroup betweenness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)

Cites Work

• A threshold of ln n for approximating set cover
• Emergence of Scaling in Random Networks
• The centrality of groups and classes
• A faster algorithm for betweenness centrality*
• CONGESTION AND CENTRALITY IN TRAFFIC FLOW ON COMPLEX NETWORKS
• Title not available (Why is that?)

Cited In (9)

• Heuristical top-\(k\): fast estimation of centralities in complex networks
• Finding groups with maximum betweenness centrality
• Potential-based bounded-cost search and anytime non-parametric A*
• Group centralization of network indices
• Finding groups with maximum betweenness centrality via integer programming with random path sampling
• Maximum Betweenness Centrality: Approximability and Tractable Cases
• An integer programming approach for finding the most and the least central cliques
• A survey on optimization studies of group centrality metrics
• Novel centrality metrics for studying essentiality in protein‐protein interaction networks based on group structures

This page was built for publication: Incremental deployment of network monitors based on Group Betweenness Centrality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990953)