Incremental deployment of network monitors based on Group Betweenness Centrality

DOI10.1016/J.IPL.2009.07.019MaRDI QIDQ990953zbMATH OpenOpenAlexFDO

Authors Shlomi Dolev, Yuval Elovici, Rami Puzis, Polina Zilberman

Publication date 1 September 2010

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5663542 (Why is no real title available?)
• A faster algorithm for betweenness centrality*
• A threshold of ln n for approximating set cover
• CONGESTION AND CENTRALITY IN TRAFFIC FLOW ON COMPLEX NETWORKS
• Emergence of Scaling in Random Networks
• The centrality of groups and classes

Cited in

(9)

• Heuristical top-\(k\): fast estimation of centralities in complex networks
• Finding groups with maximum betweenness centrality
• Maximum betweenness centrality: approximability and tractable cases
• 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
• 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)