Rethinking centrality: The role of dynamical processes in social network analysis

Rumi Ghosh; Kristina Lerman

doi:10.3934/dcdsb.2014.19.1355

Article Contents

2014, Volume 19, Issue 5: 1355-1372. Doi: 10.3934/dcdsb.2014.19.1355

This issue Previous Article Latent self-exciting point process model for spatial-temporal networks Next Article The stability of steady-state hot-spot patterns for a reaction-diffusion model of urban crime

Rethinking centrality: The role of dynamical processes in social network analysis

Rumi Ghosh^1, and
Kristina Lerman^2,

1.
Robert Bosch LLC, 4005 Miranda Ave, Palo Alto, CA 94304
2.
USC Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA 90292

Received: January 2012

Revised: June 2012

Published: July 2014

Abstract / Introduction Related Papers Cited by

Abstract

Many popular measures used in social network analysis, including centrality, are based on the random walk. The random walk is a model of a stochastic process where a node interacts with one other node at a time. However, the random walk may not be appropriate for modeling social phenomena, including epidemics and information diffusion, in which one node may interact with many others at the same time, for example, by broadcasting the virus or information to its neighbors. To produce meaningful results, social network analysis algorithms have to take into account the nature of interactions between the nodes. In this paper we classify dynamical processes as conservative and non-conservative and relate them to well-known measures of centrality used in network analysis: PageRank and Alpha-Centrality. We demonstrate, by ranking users in online social networks used for broadcasting information, that non-conservative Alpha-Centrality generally leads to a better agreement with an empirical ranking scheme than the conservative PageRank.

Keywords:

Mathematics Subject Classification: Primary: 91D30, 68R10; Secondary: 62P25, 37A60.

Citation:

Related Papers

Cited by

References

[1]	R. M. Anderson and R. May, Infectious Diseases of Humans: Dynamics and Control, Oxford University Press, 1991.
[2]	N. Bailey, The Mathematical Theory of Infectious Diseases and its Applications, Griffin, London, 1975.
[3]	E. Bakshy, J. M. Hofman, W. A. Mason and D. J. Watts, Everyone's an influencer: Quantifying influence on twitter, in Proc. the fourth ACM Int. Conf. on Web search and data mining, New York, NY, USA, (2011), 65-74.doi: 10.1145/1935826.1935845.
[4]	A. Barrat, M. Barthélemy and A. Vespignani, Dynamical Processes on Complex Networks, 1st edition, Cambridge University Press, Cambridge, England, 2008.doi: 10.1017/CBO9780511791383.
[5]	L. M. A. Bettencourt, A. Cintrón-Arias, D. I. Kaiser and C. Castillo-Chávez, The power of a good idea: Quantitative modeling of the spread of ideas from epidemiological models, Physica A: Statistical Mechanics and its Applications, 364 (2006), 513-536.doi: 10.1016/j.physa.2005.08.083.
[6]	P. Boldi, M. Santini and S. Vigna, Pagerank as a function of the damping factor, in Proc. the 14th Int. Conf. on World Wide Web, (2005), 557-566.doi: 10.1145/1060745.1060827.
[7]	P. Bonacich, Factoring and weighting approaches to status scores and clique identification, Journal of Mathematical Sociology, 2 (1972), 113-120.doi: 10.1080/0022250X.1972.9989806.
[8]	P. Bonacich, Power and centrality: A family of measures, The American Journal of Sociology, 92 (1987), 1170-1182.doi: 10.1086/228631.
[9]	P. Bonacich and P. Lloyd, Eigenvector-like measures of centrality for asymmetric relations, Social Networks, 23 (2001), 191-201.doi: 10.1016/S0378-8733(01)00038-7.
[10]	S. Borgatti, Centrality and network flow, Social Networks, 27 (2005), 55-71.doi: 10.1016/j.socnet.2004.11.008.
[11]	S. Borgatti and M. Everett, A graph-theoretic perspective on centrality, Social Networks, 28 (2006), 466-484.doi: 10.1016/j.socnet.2005.11.005.
[12]	J. J. Brown and P. H. Reingen, Social ties and Word-of-Mouth referral behavior, The Journal of Consumer Research, 14 (1987), 350-362.doi: 10.1086/209118.
[13]	D. Centola and M. Macy, Complex contagions and the weakness of long ties, American Journal of Sociology, 113 (2007), 702-734.doi: 10.1086/521848.
[14]	M. Cha, H. Haddadi, F. Benevenuto and K. P. Gummadi, Measuring User Influence in Twitter: The Million Follower Fallacy, in Proc. 4th Int. Conf. on Weblogs and Social Media (ICWSM), 2010.
[15]	K. Dietz, The estimation of the basic reproduction number for infectious diseases, Statistical methods in medical research, 2 (1993), 23-41.doi: 10.1177/096228029300200103.
[16]	E. Estrada, N. Hatano and M. Benzi, The physics of communicability in complex networks, Physics Reports, 514 (2012), 89-119.doi: 10.1016/j.physrep.2012.01.006.
[17]	S. Fortunato and A. Flammini, Random walks on directed networks: The case of pageRank, International Journal of Bifurcation and Chaos, 17 (2007), 2343-2353.doi: 10.1142/S0218127407018439.
[18]	L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry, 40 (1977), 35-41.doi: 10.2307/3033543.
[19]	F. Gebali, Markov chains., Analysis of Computer and Communication Networks, 65:122.
[20]	R. Ghosh and K. Lerman, Predicting Influential Users in Online Social Networks, in Proc. KDD workshop on Social Network Analysis (SNAKDD), 2010.
[21]	R. Ghosh and K. Lerman, A Framework for Quantitative Analysis of Cascades on Networks, in Proc. Web Search and Data Mining Conference (WSDM), (2011), 665-674.doi: 10.1145/1935826.1935917.
[22]	R. Ghosh and K. Lerman, Parameterized centrality metric for network analysis, Physical Review E, 83 (2011), 066118+.doi: 10.1103/PhysRevE.83.066118.
[23]	R. Ghosh, T. Surachawala and K. Lerman, Entropy-based classification of ‘retweeting' activity on twitter, in Proc. KDD workshop on Social Network Analysis (SNA-KDD), 2011.
[24]	D. F. Gleich, P. G. Constantine, A. D. Flaxman and A. Gunawardana, Tracking the random surfer: Empirically measured teleportation parameters in PageRank, in Proc. 19th international conference on World wide web, (2010), 381-390.doi: 10.1145/1772690.1772730.
[25]	S. Goel, D. J. Watts and D. G. Goldstein, The structure of online diffusion networks, in Proc. 13th ACM Conference on Electronic Commerce (EC 2012), (2012), 623-638, URL http://5harad.com/papers/diffusion.pdf.doi: 10.1145/2229012.2229058.
[26]	J. Goldenberg, B. Libai and E. Muller, Talk of the network: A complex systems look at the underlying process of word-of-mouth, Marketing Letters, 211-223.
[27]	H. W. Hethcote, The mathematics of infectious diseases, SIAM Review, 42 (2000), 599-653.doi: 10.1137/S0036144500371907.
[28]	N. Hodas and K. Lerman, How limited visibility and divided attention constrain social contagion, in submitted to Social Computing, 2012.
[29]	N. O. Hodas and K. Lerman, The simple rules of social contagion, Scientific Reports, 4, 2014.doi: 10.1038/srep04343.
[30]	T. Hogg and K. Lerman, Stochastic models of user-contributory web sites, in Proc. 3rd Int. Conf. on Weblogs and Social Media (ICWSM), 2009.
[31]	T. Hogg and K. Lerman, Social Dynamics of Digg, EPJ Data Science, 5 (2012).
[32]	J. L. Iribarren and E. Moro, Impact of human activity patterns on the dynamics of information diffusion, Physical Review Letters, 103 (2009), 038702+.doi: 10.1103/PhysRevLett.103.038702.
[33]	G. Jeh and J. Widom, Scaling personalized web search, in Proc. the 12th Int. Conf. on World Wide Web, New York, NY, USA, (2003), 271-279.doi: 10.1145/775189.775191.
[34]	E. Katz and P. Lazarsfeld, Personal Influence: The Part Played by People in the Flow of Mass Communications, Transaction Publishers, 2005.
[35]	L. Katz, A new status index derived from sociometric analysis, Psychometrika, 18 (1953), 39-43.doi: 10.1007/BF02289026.
[36]	D. Kempe, J. Kleinberg and E. Tardos, Maximizing the spread of influence through a social network, KDD '03 Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, (2003), 137-146.doi: 10.1145/956755.956769.
[37]	C. Kiss and M. Bichler, Identiffication of influencers-measuring influence in customer networks, Decision Support Systems, 46 (2008), 233-253.
[38]	S. Kotz and N. Balakrishnan, Advances in urn models during the past two decades, in Advances in combinatorial methods and applications to probability and statistics, Birkhauser Boston, Boston, 1997, 203-257.
[39]	R. Lambiotte, J. C. Delvenne and M. Barahona, Laplacian dynamics and multiscale modular structure in networks.
[40]	R. Lambiotte, R. Sinatra, J. C. Delvenne, T. S. Evans, M. Barahona and V. Latora, Flow graphs: Interweaving dynamics and structure, Physical Review E, 84 (2011), 017102+.doi: 10.1103/PhysRevE.84.017102.
[41]	C. Lee, H. Kwak, H. Park and S. Moon, Finding Influentials from Temporal Order of Information Adoption in Twitter, Proc. 19th World-Wide Web (WWW) Conference (Poster), 2010.
[42]	K. Lerman and R. Ghosh, Information Contagion: An Empirical Study of the Spread of News on Digg and Twitter Social Networks, Proc. 4th Int. Conf. on Weblogs and Social Media (ICWSM), 2010.
[43]	L. Page, S. Brin, R. Motwani and T. Winograd, The PageRank Citation Ranking: Bringing Order to the Web, Technical report, Stanford Digital Library Technologies Project, 1998.
[44]	R. Pastor-Satorras and A. Vespignani, Epidemic spreading in scale-free networks, Physical Review Letters, 86 (2001), 3200-3203.doi: 10.1103/PhysRevLett.86.3200.
[45]	B. A. Prakash, D. Chakrabartiy, M. Faloutsos, N. Valler and C. Faloutsos, Threshold conditions for arbitrary cascade models on arbitrary networks, in Proc. the Int. Conf. on Data Mining, (2011), 537-546.doi: 10.1109/ICDM.2011.145.
[46]	E. M. Rogers, Diffusion of Innovations, 5th Edition, Free Press, 2003.
[47]	D. M. Romero, W. Galuba, S. Asur and B. A. Huberman, Influence and passivity in social media, in Proc. the 20th international Conference on World wide web, (2011), 113-114.doi: 10.1145/1963192.1963250.
[48]	H. Tong, C. Faloutsos and J. Pan, Fast random walk with restart and its applications, in ICDM '06: Proc. the Sixth Int. Conf. on Data Mining, Washington, DC, USA, 2006, 613-622.doi: 10.1109/ICDM.2006.70.
[49]	M. Trusov, A. V. Bodapati and R. E. Bucklin, Determining influential users in internet social networks, Journal of Marketing Research, 47 (2010), 643-658.doi: 10.1509/jmkr.47.4.643.
[50]	G. Ver Steeg, R. Ghosh and K. Lerman, What stops social epidemics?, in Proc. 5th International AAAI Conference on Weblogs and Social Media (ICWSM), 2011.
[51]	Y. Wang, D. Chakrabarti, C. Wang and C. Faloutsos, Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint, Reliable Distributed Systems, IEEE Symposium on, 0 (2003), 25+.
[52]	D. J. Watts and P. S. Dodds, Influentials, networks, and public opinion formation, Journal of Consumer Research, 34 (2007), 441-458.doi: 10.1086/518527.