nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2013 | Original Article

Identifying high betweenness centrality nodes in large social networks

verfasst von: Nicolas Kourtellis, Tharaka Alahakoon, Ramanuja Simha, Adriana Iamnitchi, Rahul Tripathi

Erschienen in: Social Network Analysis and Mining | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper proposes an alternative way to identify nodes with high betweenness centrality. It introduces a new metric, κ-path centrality, and a randomized algorithm for estimating it, and shows empirically that nodes with high κ-path centrality have high node betweenness centrality. The randomized algorithm runs in time O(κ³ n ^2−2αlog n) and outputs, for each vertex v, an estimate of its κ-path centrality up to additive error of ±n ^1/2+α with probability 1 − 1/n ². Experimental evaluations on real and synthetic social networks show improved accuracy in detecting high betweenness centrality nodes and significantly reduced execution time when compared with existing randomized algorithms.

Vorheriger Artikel On the impact of text similarity functions on hashtag recommendations in microblogging environments

Nächster Artikel Identifying statistically significant edges in one-mode projections

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The Hoeffding bound (Hoeffding 1963), a classical result in probability theory, states the following: Let \(X_{1}, X_{2}, \ldots, X_{T}\) be independent random variables, such that each X _i ranges over the real interval [a _i, b _i], and let \(\mu = E[\sum\nolimits_{i=1}^{T} X_{i}/{T}]\) denote the expected value of the average of these variables. Then, for every ξ > 0, \({\rm \hbox{Pr}}[|\frac{\sum_{i=1}^{T} X_{i}}{T} - \mu| \geq \xi] \leq 2e^{-2T^{2}\xi^{2}/\sum_{i=1}^{T} (b_{i} - a_{i})^{2}}. \)

Alahakoon T, Tripathi R, Kourtellis N, Simha R, Iamnitchi A (2011) K-path centrality: a new centrality measure in social networks. In: 4th ACM EuroSys workshop on social network systems

Ang CS (2011) Interaction networks and patterns of guild community in massively multiplayer online games. Soc Netw Anal Min 1(4):341–353CrossRef

Anthonisse J (1971) The rush in a directed graph. Technical Report BN9/71. Stichting Mathematisch Centrum, Amsterdam

Bader D, Kintali S, Madduri K, Mihail M (2007) Approximating betweenness centrality. In: 5th Workshop on algorithms and models for the web-graph, pp 124–137

Batagelj V, Mrvar A (2006) Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/

Blackburn J, Simha R, Kourtellis N, Zuo X, Ripeanu M, Skvoretz J, Iamnitchi A (2012) Branded with a scarlet C: cheaters in a gaming social network. In: 21st International conference on world wide web, Lyon, France

Borgatti S, Everett M (2006) A graph-theoretic perspective on centrality. Soc Netw 28(4):466–484CrossRef

Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163–177CrossRefMATH

Brandes U (2008) On variants of shortest-path betweenness centrality and their generic computation. Soc Netw 30(2):136–145MathSciNetCrossRef

Brandes U, Fleischer D (2005) Centrality measures based on current flow. In: Proceedings of the 22nd annual symposium on theoretical aspects of computer science, Lecture notes in computer science, vol 3404. Springer, pp 533–544

Brandes U, Pich C (2007) Centrality estimation in large networks. Int J Bifurc Chaos 17(7):2303–2318 (Special Issue on Complex Networks Structure and Dynamics)MathSciNetCrossRefMATH

Catanese S, Ferrara E, Fiumara G (2012) Forensic analysis of phone call networks. Soc Netw Anal Min. doi:10.1007/s13278-012-0060-1

Eppstein D, Wang J (2004) Fast approximation of centrality. J Graph Algorithms Appl 8(1):39–45MathSciNetCrossRefMATH

Freeman L (1977) A set of measures of centrality based on betweenness. Sociometry 40(1):35–41CrossRef

Freeman C, Borgatti S, White D (1991) Centrality in valued graphs: A measure of betweenness based on network flow. Soc Netw 13(2):141–154MathSciNetCrossRef

Friedkin N (1983) Horizons of observability and limits of informal control in organizations. Soc Forces, 62(1):57–77

Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Am Stat Assoc 58:13–30MathSciNetCrossRefMATH

Hua G, Haughton D (2012) A network analysis of an online expertise sharing community. Soc Netw Anal Min. doi:10.1007/s13278-012-0047-y

Iamnitchi A, Ripeanu M, Foster I (2004) Small-world file-sharing communities. In: 23rd Conf. of the IEEE Communications Society (InfoCom), pp 952–963

Jacob R, Koschützki D, Lehmann K, Peeters L, Podehl D (2005) Algorithms for centrality indices. In Network Analysis, volume 3418 of LNCS, Springer, pp 62–82

Jeong H, Mason S, Barabási A, Oltvai Z (2001) Lethality and centrality in protein networks. Nature 411:41CrossRef

Kahng G, Oh E, Kahng B, Kim D (2003) Betweenness centrality correlation in social networks. Phys Rev E 67:01710–01711

Kourtellis N, Iamnitchi A (2011) Inferring peer centrality in socially-informed peer-to-peer systems. In: 11th IEEE International conference on Peer-to-Peer computing, Kyoto, Japan

Leskovec J (2011) Stanford large network dataset collection. http://snap.stanford.edu/data/

Liljeros F, Edling C, Amaral L, Stanley H, Aberg Y (2001) The web of human sexual contacts. Nature 411:907CrossRef

Lipton R, Naughton J (1989) Estimating the size of generalized transitive closures. In: 15th International conference on very large databases. Morgan Kaufmann, San Francisco, pp 165–171

Macskassy S (2011) Contextual linking behavior of bloggers: leveraging text mining to enable topic-based analysis. Soc Netw Anal Min 1(4):355–375CrossRef

Maglaras LA, Katsaros D (2011) New measures for characterizing the significance of nodes in wireless ad hoc networks via localized path-based neighborhood analysis. Soc Netw Anal Min. doi:10.1007/s13278-011-0029-5

Newman M (2001) The structure of scientific collaboration networks. Proc Nat Acad Sci USA 98(2):404–409CrossRefMATH

Newman M (2005) A measure of betweenness centrality based on random walks. Soc Netw 27(1):39–54CrossRef

Ortiz M, Hoyos J, Lopez M (2004) The social networks of academic performance in a student context of poverty in Mexico. Soc Netw 26(2):175–188CrossRef

Ripeanu M, Iamnitchi A, Foster I (2002) Mapping the Gnutella network. Internet Comput IEEE 6(1):50–57CrossRef

Said Y, Wegman E, Sharabati W, Rigsby J (2008) Social networks of author-coauthor relationships. Comput Stat Data Anal 52:2177–2184MathSciNetCrossRef

Sala A, Cao L, Wilson C, Zablit R, Zheng H, Zhao B (2010) Measurement-calibrated graph models for social network experiments. In: 19th International conference on world wide web, pp 861–870

Singh B, Gupte N (2005) Congestion and decongestion in a communication network. Phys Rev E 71(5):055103CrossRef

Stephenson K, Zelen M (1989) Rethinking centrality: methods and examples. Soc Netw 11:1–37MathSciNetCrossRef

Titel: Identifying high betweenness centrality nodes in large social networks
verfasst von: Nicolas Kourtellis
Tharaka Alahakoon
Ramanuja Simha
Adriana Iamnitchi
Rahul Tripathi
Publikationsdatum: 01.12.2013
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 4/2013
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-012-0076-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2013

Hypergraph index: an index for context-aware nearest neighbor query on social networks

Social recommendation: a review

Robustness of social and web graphs to node removal

On learning cluster coefficient of private networks

Probabilistic analysis of communities and inner roles in networks: Bayesian generative models and approximate inference

Robust features of trust in social networks