Point centrality indices and ISP network vulnerability
Speaker: George Nomikos
Date: 11 April 2014 Time: 12:30
Location: "Alkiviades C. Payatakes" Seminar Room, FORTH, Heraklion, Crete
Host: Xenofontas Dimitropoulos


Social Network Analysis (SNA) primarily studies the networks with graph-theoretic tools modeling individual actors within the network as the nodes and their relationships as the links of a graph. One of the SNA fundamentals is the notion of point centrality which was designed to reflect the relevant social significance among actors and has lately come to the attention of computer scientists; the latter seeks to identify highly central network nodes that can be exploited in the design of efficient protocols. This work studies the concept of centrality along three lines: Our first contribution is then an exhaustive survey and categorization of centrality indices that have been proposed over the last 40 years or so, along several attributes including the type of information (local vs. global) and processing complexity required for their computation. We next study the seven most popular of those indices in the context of Internet vulnerability to address issues that remain underexplored in literature so far. First, we carry out a correlation study to assess the consistency of the node rankings those indices generate over ISP router-level topologies. For each pair of indices, we computed the full ranking correlation, which is the standard choice in literature, and the percentage overlap between the k top nodes. Then, we let these rankings guide the removal of highly central nodes and assess the impact on both the connectivity properties and traffic-carrying capacity of the network. Our results confirm that the top-k overlap predicts the comparative impact of indices on the network vulnerability better than the full-ranking correlation. Importantly, the locally computed degree centrality index approximates closely the global indices with the most dramatic impact on the traffic-carrying capacity; whereas, is approximate power in terms of connectivity is more topology-dependent.


George Nomikos was born in Athens in 1988 and he is currently finishing his military service in Heraklion. In 2009 he joined the TNL Lab of ICS-FORTH under the supervision of Prof. Maria Papadopouli and the same year he followed, as an erasmus student, the Communication Systems Group headed by Prof. Bernhard Plattner at ETH Zurich, in Switzerland until 2010. In 2011, he received his Bachelor's Degree in Computer Science majoring in networking from the Computer Science Department in the University of Crete. Two years later in 2013 he acquired his Master's degree from the National & Kapodistrian University of Athens in the field of Communications Systems & Networks advised by Dr. Merkourios Karaliopoulos and Prof. Ioannis Stavrakakis, head of the Advanced Networking Research group.

His research interests include performance analysis on wireless mesh networks (WMNs), networking activity assessment under online social networks (OSNs), graph theoretic concepts and wireless networking security.

Conditions of Use | Privacy Policy