Fragkiskos D. Malliaros
ABSTRACT
Given a large social graph, how can we model the engagement properties of nodes? Can we quantify engagement both at node level as well as at graph level? Typically, engagement refers to the degree that an individual participates (or is encouraged to participate) in a community and is closely related to the important property of nodes' departure dynamics, i.e., the tendency of individuals to leave the community. In this paper, we build upon recent work in the field of game theory, where the behavior of individuals (nodes) is modeled by a technology adoption game. That is, the decision of a node to remain engaged in the graph is affected by the decision of its neighbors, and the "best practice" for each individual is captured by its core number - as arises from the k-core decomposition. After modeling and defining the engagement dynamics at node and graph level, we examine whether they depend on structural and topological features of the graph. We perform experiments on a multitude of real graphs, observing interesting connections with other graph characteristics, as well as a clear deviation from the corresponding behavior of random graphs. Furthermore, similar to the well known results about the robustness of real graphs under random and targeted node removals, we discuss the implications of our findings on a special case of robustness - regarding random and targeted node departures based on their engagement level.
- The DBLP Computer Science Bibliography, http://www.informatik.uni-trier.de/~ley/db/.Google Scholar
- R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys., 74:47--97, 2002.Google ScholarCross Ref
- J. I. Alvarez-Hamelin, , L. Dall'Asta, A. Barrat, and A. Vespignani. k-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. NHM, 3(2):371, 2008.Google ScholarCross Ref
- A. Anagnostopoulos, R. Kumar, and M. Mahdian. Influence and correlation in social networks. In KDD, pages 7--15, 2008. Google ScholarDigital Library
- L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In KDD, pages 44--54, 2006. Google ScholarDigital Library
- R. Baeza-Yates and M. Lalmas. User engagement:the network effect matters! In CIKM, 2012. Google ScholarDigital Library
- V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks. CoRR, 2003.Google Scholar
- K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma. Preventing unraveling in social networks: the anchored k-core problem. In ICALP, pages 440--451. 2011. Google ScholarDigital Library
- S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, and E. Shir. A model of internet topology using k-shell decomposition. PNAS, 104(27):11150--11154, 2007.Google ScholarCross Ref
- D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY, USA, 2010. Google ScholarDigital Library
- D. F. Gleich and C. Seshadhri. Vertex neighborhoods, low conductance cuts, and good seeds for local community methods. In KDD, pages 597--605, 2012. Google ScholarDigital Library
- A. Harkins. Network games with perfect complements. Technical report, University of Warwick, February 2013.Google Scholar
- M. Kitsak, L. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. Stanley, and H. Makse. Identification of influential spreaders in complex networks. Nature Physics, 6(11):888--893, Aug 2010.Google ScholarCross Ref
- S. Lattanzi and D. Sivakumar. Affiliation networks. In STOC, pages 427--434, 2009. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM TKDD, 1(1), 2007. Google ScholarDigital Library
- J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large welldefined clusters. Internet Mathematics, 6(1):29--123, 2009.Google ScholarCross Ref
- V. H. Manshadi and R. Johari. Supermodular network games. In Allerton, pages 1369--1376, 2009. Google ScholarDigital Library
- A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and analysis of online social networks. In IMC, pages 29--42, 2007. Google ScholarDigital Library
- B. Pittel, J. Spencer, and N. Wormald. Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B, 67(1):111--151, 1996. Google ScholarDigital Library
- M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In ISWC, pages 351--368, 2003.Google ScholarDigital Library
- D. M. Romero, B. Meeder, and J. Kleinberg. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In WWW, pages 695--704, 2011. Google ScholarDigital Library
- S. B. Seidman. Network structure and minimum degree. Social Networks, 5:269--287, 1983.Google ScholarCross Ref
- J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural diversity in social contagion. PNAS, 109(16):5962--5966, 2012.Google ScholarCross Ref
- B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi. On the evolution of user interaction in facebook. In WOSN, pages 37--42, 2009. Google ScholarDigital Library
- S. Wu, A. Das Sarma, A. Fabrikant, S. Lattanzi, and A. Tomkins. Arrival and departure dynamics in social networks. In WSDM, pages 233--242, 2013. Google ScholarDigital Library
- Y. Zhang and S. Parthasarathy. Extracting analyzing and visualizing triangle k-core motifs within networks. In ICDE, pages 1049--1060, 2012. Google ScholarDigital Library
Index Terms
- To stay or not to stay: modeling engagement dynamics in social graphs
Recommendations
Estimating robustness in large social graphs
Given a large social graph, what can we say about its robustness? Broadly speaking, the property of robustness is crucial in real graphs, since it is related to the structural behavior of graphs to retain their connectivity properties after losing a ...
Advanced graph mining for community evaluation in social networks and the web
WSDM '13: Proceedings of the sixth ACM international conference on Web search and data miningGraphs constitute a dominant data structure and appear essentially in all forms of information. Examples are the Web graph, numerous social networks, protein interaction networks, terms dependency graphs and network topologies. The main features of ...
Comments