Dresden 2006 – scientific programme
Parts | Days | Selection | Search | Downloads | Help
AKSOE: Physik sozio-ökonomischer Systeme
AKSOE 10: Poster Session (posters are expected to be displayed the full day 8:30-18:00)
AKSOE 10.47: Poster
Wednesday, March 29, 2006, 16:00–18:00, P2
Correlations of centrality metrics on complex networks — •Magnus Jungsbluth and Alexander K. Hartmann — Institut für theoretische Physik, Universität Göttingen, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany
The study of complex networks plays a crucial role in understanding systems like metabolic pathways, collaborations and computer networks. A popular task is to identify the most important nodes of a network. There are several definitions, often called centrality measures, which lead to different results. The most prominent centrality measure is the degree of a node which is easy to obtain. For many real-world networks, the degree distribution follows a power law and hence these networks are often called scale-free. Another frequently used measure is the betweeness centrality which is based on calculating shortest-paths. Recently other centrality measures have been proposed, based on random walks or on participation in subgraphs. Yet it is not clear under what circumstances which measure is most appropriate and what the relations between these measures are.
Here we study correlations between the above mentioned four measures on different random-graph models like Erdös-Renyi, Small-World and Barabasi-Albert and on several real graphs to get a thorough comparasion and to be able to identify which measure is the best suited one for each individual situation. Since at least the last two measures are expensive to calculate (running time slightly above O(n3) for n nodes) we look at how accurate approximations are if only a small subset of the whole network is considered.