research-article

Centralities: capturing the fuzzy notion of importance in social graphs

Authors:

Erwan Le Merrer,

Gilles TrédanAuthors Info & Claims

SNS '09: Proceedings of the Second ACM EuroSys Workshop on Social Network Systems

Pages 33 - 38

https://doi.org/10.1145/1578002.1578008

Published: 31 March 2009 Publication History

Abstract

The increase of interest in the analysis of contemporary social networks, for both academic and economic reasons, has highlighted the inherent difficulties in handling large and complex structures. Among the tools provided by researchers for network analysis, the centrality notion, capturing the importance of individuals in a graph, is of particular interest. Despite many definitions and implementations of centrality, no clear advantage is given to a particular paradigm for the study of social network characteristics. In this paper we review, compare and highlight the strengths of different definitions of centralities in contemporary social networks.

References

[1]

Serge Abiteboul, Mihai Preda, and Gregory Cobena. Adaptive on-line page importance computation. In WWW '03: Proceedings of the 12th international conference on World Wide Web, pages 280--290, New York, NY, USA, 2003.

Digital Library

[2]

R. Albert and A.-L. Barab&#225;si. Statistical mechanics of complex networks. Reviews of Modern Physics, 74:47--97, 2002.

[3]

Reka Albert, Hawoong Jeong, and Albert-Laszlo Barabasi. Error and attack tolerance of complex networks. Nature, 406:378, 2000.

[4]

D. Anthony. Social network analysis in military headquarters using cavalier. In 5th International Command, Control Research and Technology Symposium.

[5]

David Bader, Shiva Kintali, Kamesh Madduri, and Milena Mihail. Approximating betweenness centrality. pages 124--137. 2007.

[6]

P Bonacich. Factoring and weighting approaches to status scores and clique identification. J. Math. Social. 2, pages 113--120, 1972.

[7]

Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25:163--177, 2001.

[8]

Ulrik Brandes and Christian Pich. Centrality estimation in large networks. International Journal of Bifurcation and Chaos, pages 2303--2318, 2007.

[9]

Tim Dwyer, Seok-Hee Hong, Dirk Kosch&#252;tzki, Falk Schreiber, and Kai Xu. Visual analysis of network centralities. In APVis '06: Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation, pages 189--197, Darlinghurst, Australia, Australia, 2006. Australian Computer Society, Inc.

Digital Library

[10]

David Eppstein and Joseph Wang. Fast approximation of centrality. In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 228--229, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.

Digital Library

[11]

D&#225;niel Fogaras. Where to start browsing the web. In IICS: nnovative internet community systems, pages 65--79. Springer-Verlag, 2003.

[12]

Linton C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35--41, March 1977.

[13]

Linton C. Freeman. Centrality in social networks: Conceptual clarification. Social Networks, 1(3):215--239, 1979.

[14]

Robert Geisberger, Peter Sanders, and Dominik Schultes. Better approximation of betweenness centrality. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), 2008.

[15]

Pablo Gleiser and Leon Danon. Community structure in jazz. Advances in Complex Systems, 6:565, 2003.

[16]

Per Hage and Frank Harary. Eccentricity and centrality in networks. Social Networks, 17(1):57--63, 1995.

[17]

K. i. Goh, E. Oh, B. Kahng, and D. Kim. Betweenness centrality correlation in social networks. Phys. Rev. E, 67:01710-1, 2003.

[18]

Saroja Kanchi and David Vineyard. An optimal distributed algorithm for all-pairs shortest-path. Information theories and applications, 11:141--146, 2004.

[19]

A.-M. Kermarrec, E. Le Merrer, B. Sericola, and G. Tr&#233;dan. Rr-6809 inria - second order centrality: distributed assessment of nodes criticity in complex networks, 2009.

[20]

V. Latora and M. Marchiori. A measure of centrality based on network efficiency. New Journal of Physics, 9(188), 2007.

[21]

Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 631--636, New York, NY, USA, 2006. ACM.

Digital Library

[22]

Soumendra Nanda and David Kotz. Localized bridging centrality for distributed network analysis. In Proceedings of the 17th International Conference on Computer Communications and Networks (ICCCN), pages 1--6, August 2008.

[23]

Newman. A measure of betweenness centrality based on random walks. Social Networks, 27(1):39--54, January 2005.

[24]

Kazuya Okamoto, Wei Chen, and Xiang-Yang Li. Ranking of closeness centrality for large-scale social networks. In FAW '08: Proceedings of the 2nd annual international workshop on Frontiers in Algorithmics, pages 186--195, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

[25]

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.

[26]

Muhammad Akram Shaikh, Jiaxin Wang, Zehong Yang, and Yixu Song. Graph structural mining in terrorist networks. In ADMA '07: Proceedings of the 3rd international conference on Advanced Data Mining and Applications, pages 570--577, Berlin, Heidelberg, 2007. Springer-Verlag.

Digital Library

[27]

Jeffrey Travers and Stanley Milgram. An experimental study of the small world problem. Sociometry, 32(4):425--443, 1969.

[28]

Stanley Wasserman, Katherine Faust, and Dawn Iacobucci. Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences). Cambridge University Press, November 1994.

[29]

Eiko Yoneki, Pan Hui, ShuYan Chan, and Jon Crowcroft. A socio-aware overlay for publish/subscribe communication in delay tolerant networks. In MSWiM '07: Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, pages 225--234, New York, NY, USA, 2007. ACM.

Digital Library

Cited By

Miftah AWidianingsih IMuhtar ESutriadi R(2024)Behind the scenes of COVID-19 response: a social network analysis of policy actors in Bandung CityCogent Social Sciences10.1080/23311886.2024.235635110:1Online publication date: 14-Jun-2024
https://doi.org/10.1080/23311886.2024.2356351
Tunçel Gölpek HAytaç A(2023)Computing closeness for some graphsActa Universitatis Sapientiae, Informatica10.2478/ausi-2023-001515:2(221-238)Online publication date: 12-Dec-2023
https://doi.org/10.2478/ausi-2023-0015
Ozkaya MSanyuce APinar ACatalyurek U(2018)Local Detection of Critical Nodes in Active Graphs2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)10.1109/ASONAM.2018.8508323(107-110)Online publication date: Aug-2018
https://doi.org/10.1109/ASONAM.2018.8508323
Show More Cited By

Index Terms

Recommendations

k-Centralities: local approximations of global measures based on shortest paths
WWW '12 Companion: Proceedings of the 21st International Conference on World Wide Web

A lot of centrality measures have been developed to analyze different aspects of importance. Some of the most popular centrality measures (e.g. betweenness centrality, closeness centrality) are based on the calculation of shortest paths. This ...
Correlating centralities of social networks
2016 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS)
Centrality is an important measure to identify the most important actors in a network. This paper discusses the various Centrality Measures used in Social Network Analysis. These measures are tested on complex real-world social network data sets such as ...
On eigenvector-like centralities for temporal networks

Centrality measures play a central role in Complex Networks Theory as much as they provide a tool to rank nodes by their relevance in the processes occurring in a network. In this paper we propose a model for the eigenvector-like centralities of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SNS '09: Proceedings of the Second ACM EuroSys Workshop on Social Network Systems

March 2009

58 pages

ISBN:9781605584638

DOI:10.1145/1578002

Program Chairs:
Tao Stein
Facebook
,
Meeyoung Cha
Max Planck Institure for Software Systems

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 March 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

EuroSys '09

Sponsor:

SIGOPS

EuroSys '09: Fourth EuroSys Conference 2009

March 31, 2009

Nuremberg, Germany

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Miftah AWidianingsih IMuhtar ESutriadi R(2024)Behind the scenes of COVID-19 response: a social network analysis of policy actors in Bandung CityCogent Social Sciences10.1080/23311886.2024.235635110:1Online publication date: 14-Jun-2024
https://doi.org/10.1080/23311886.2024.2356351
Tunçel Gölpek HAytaç A(2023)Computing closeness for some graphsActa Universitatis Sapientiae, Informatica10.2478/ausi-2023-001515:2(221-238)Online publication date: 12-Dec-2023
https://doi.org/10.2478/ausi-2023-0015
Ozkaya MSanyuce APinar ACatalyurek U(2018)Local Detection of Critical Nodes in Active Graphs2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)10.1109/ASONAM.2018.8508323(107-110)Online publication date: Aug-2018
https://doi.org/10.1109/ASONAM.2018.8508323
Sarıyüce ASaule EKaya KÇatalyürek Ü(2015)Incremental closeness centrality in distributed memoryParallel Computing10.1016/j.parco.2015.01.00347:C(3-18)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.parco.2015.01.003
Sarıyüce ASaule EKaya KÇatalyürek U(2015)Regularizing graph centrality computationsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2014.07.00676:C(106-119)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2014.07.006
Ji WCao X(2014)Measurement and Analysis Topological Characteristics of Video-Sharing NetworkApplied Mechanics and Materials10.4028/www.scientific.net/AMM.575.863575(863-868)Online publication date: Jun-2014
https://doi.org/10.4028/www.scientific.net/AMM.575.863
Sariyuce ASaule EKaya KÇatalyürek Ü(2014)Hardware/Software Vectorization for Closeness Centrality on Multi-/Many-Core ArchitecturesProceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops10.1109/IPDPSW.2014.156(1386-1395)Online publication date: 19-May-2014
https://dl.acm.org/doi/10.1109/IPDPSW.2014.156
Didimo WLiotta GMontecchiani F(2014)Network visualization for financial crime detectionJournal of Visual Languages and Computing10.1016/j.jvlc.2014.01.00225:4(433-451)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1016/j.jvlc.2014.01.002
Macko PMargo DSeltzer MHe QIyengar ANejdl WPei JRastogi R(2013)Local clustering in provenance graphsProceedings of the 22nd ACM international conference on Information & Knowledge Management10.1145/2505515.2505624(835-840)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2505515.2505624
Sariyüce AKaya KSaule EÇatalyürek Ü(2013)Betweenness centrality on GPUs and heterogeneous architecturesProceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units10.1145/2458523.2458531(76-85)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2458523.2458531
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten