Group Betweenness Centrality: Efficient Computations and Applications

Rami Puzis

Complex networks are used to study the structure and dynamics of complex systems in various disciplines. For example in social networks, vertices are usually individuals and edges characterize the relations between them; in computer networks, vertices might be routers connected to each other through communication lines.In many applications we are required to locate the most prominent group of vertices in a complex network. For example, Ballester et al. state in [1] the importance of finding the key group in a criminal network. Borgatti elaborates in [2] on a Key Player Problem (KPP) that is strongly related to the cohesion of a network. Groups or routers or links that has maximal potential to control over traffic in communication networks can be used to increase the effectiveness of network measurements or intrusion detection in computer communication networks.