Madhav CHANDANE, Pranav NERURKAR, Sunil BHIRUD

Measurement of network-based and random meetings in social networks

Social networks are created by the underlying behavior of the actors involved in them. Each actor hasinteractions with other actors in the network and these interactions decide whether a social relationship should developbetween them. Such interactions may occur due to meeting processes such as chance-based meetings or network-based(choice) meetings. Depending upon which of these two types of interactions plays a greater role in creation of links, asocial network shall evolve accordingly. This evolution shall result in the social network obtaining a suitable structureand certain unique features. The aim of this work is to determine the relative ratio of the meeting processes that existbetween different actors in a social network and their importance in understanding the procedure of network formation.This is achieved by selecting a suitable network genesis model. For this purpose, different models for network genesisare discussed in detail and their differences are highlighted through experimental results. Network genesis models arecompared and contrasted with other approaches available in the literature, such as simulation-based models and blockmodels. Performance measures to compare the results of the network genesis models with baselines are statistics ofnetworks recreated using the models. The socially generated networks studied here belong to various domains like ecommerce, electoral processes, social networking websites, peer to peer file-sharing websites, and Internet graphs. Theinsights obtained after analyzing these datasets by network genesis models are used for prescribing measures that couldensure continuous growth of these social networks and improve the benefits for the actors involved in them.

PDF

___

[1] Jimenez-Martinez A. Discrimination through versioning with advertising in social networks. Econ Theor 2018; 40: 1–40.
[2] Gosak M, Markovič R, Dolenšek J, Rupnik MS, Marhl M, Stožer A, Perc M. Network science of biological systems at different scales: a review. Phys Life Rev 2018; 24: 118–135.
[3] Gosak M, Markovič R, Dolenšek J, Rupnik MS, Marhl M, Stožer A, Perc M. Loosening the shackles of scientific disciplines with network science: reply to comments on network science of biological systems at different scales: a review. Phys Life Rev 2017; 24: 162-167.
[4] Jalili M, Perc M. Information cascades in complex networks. J Compl Netw 2017; 5: 665–693.
[5] Wang Z, Yamir M, Stefano B, Perc M. Vaccination and epidemics in networked populations—an introduction. Chaos Soliton Fract 2017; 103: 177-183.
[6] Jalili M, Orouskhani Y, Asgari M, Alipourfard N, Perc M. Link prediction in multiplex online social networks. R Soc Open Sci 2017; 4: 1-11.
[7] Martinčić-Ipšić S, Močibob E, Perc M. Link prediction on Twitter. PloS one 2017; 12: 1-21.
[8] Nickel M, Kiela D. Poincare embeddings for learning hierarchical representations. Adv Neur In 2017; 31: 6338–6347.
[9] Perc M, Jordan JJ, Rand DG, Wang Z, Boccaletti S, Szolnoki A. Statistical physics of human cooperation. Phys Rep 2017; 687: 1-51.
[10] Ribeiro HV, Alves LG, Martins AF, Lenzi EK, Perc M. The dynamical structure of political corruption networks. J Compl Netw 2018; 28: 1-15.
[11] Fekom M, Coolen ACC, Lopez FA, Barucca P. Exactly solvable random graph ensemble with extensively many short cycles. J Phys A-Math Theor 2018; 33: 1-15.
[12] Rogers BW, Jackson MO. Meeting strangers and friends of friends: how random are social networks? Am Econ Rev 2007; 97: 890–915.
[13] Garas A, Schweitzer F, Tomasello MV, Napoletano M. The rise and fall of R&D networks. Ind Corp Change 2017; 726: 617–646.
[14] Zenou Y, Jackson MO, Rogers BW. The economic consequences of social-network structure. J Econ Lit 2017; 55: 49–95.
[15] Wolinsky A, Jackson MO. A strategic model of social and economic networks. Netw Grps 2003; 37: 23–49.
[16] Snijders TAB. The statistical evaluation of social network dynamics. Sociol Methodol 2001; 31: 361–395.
[17] Chandane M, Bhirud S, Nerurkar P, Shirke A. Empirical analysis of data clustering algorithms. Procedia Comput Sci 2018; 125: 770–779.
[18] Kamada Y, Iijima R. Social distance and network structures. Theor Econ 2017; 12: 655–689.
[19] Bhirud S, Nerurkar P. Modeling influence on a social network using interaction characteristics. Int J Comput Mat Sci 2017; 6: 152–160.
[20] Diaconis P, Chatterjee S. Estimating and understanding exponential random graph models. Ann Stat 2013; 41: 2428–2461.
[21] Kalish Y, Lusher D, Robins G, Pattison P. An introduction to exponential random graph (p*) models for social networks. Soc Networks 2007; 29: 173–191.
[22] Snijders TAB. Markov chain Monte Carlo estimation of exponential random graph models. J Soc Struct 2002; 183: 1–40.
[23] Zhang J, Zou X, Yang J. Microblog sentiment analysis using social and topic context. PLoS One 2018; 13: 119–163.
[24] Johari R, Leduc MV, Jackson MO. Pricing and referrals in diffusion on networks. Game Econ Behav 2017; 104: 568–594.
[25] Williams JW, Ciliberto F, Cook EE. Network structure and consolidation in the us airline industry, 1990–2015. Rev Ind Organ 2017; 10: 1-34.
[26] Kermani A, Sommavilla C, Maggio MD, Franzoni F. The relevance of broker networks for information diffusion in the stock market: technical report. Nat B Eco Research 2017; 12: 1-76.
[27] Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q. Line: Large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web; 18–22 May 2015; Florence, Italy. New York, NY, USA: International World Wide Web Conferences Steering Committee. pp. 1067–1077.
[28] Huang X, Li J, Hu X. Label informed attributed network embedding. In: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining; 6–10 February 2017; Cambridge, UK. New York, NY, USA: ACM. pp. 731–739.
[29] Huang X, Li J, Hu X. Accelerated attributed network embedding. In: Proceedings of the 2017 SIAM International Conference on Data Mining; 16–22 May 2017; Notre Dame, IN, USA. New York, NY, USA: ACM. pp. 633–641.
[30] Liao L, He X, Zhang H, Chua TS. Attributed social network embedding. arXiv preprint 2017, arXiv:1705.04969.
[31] Bandyopadhyay S, Kara H, Kannan A, Murty MN. Fscnmf: Fusing structure and content via non-negative matrix factorization for embedding information networks. arXiv preprint 2018, arXiv:1804.05313.
[32] Tsitsulin A, Mottin D, Karras P, Muller E. Verse: Versatile graph embeddings from similarity measures. In: Proceedings of the 2018 World Wide Web Conference on World Wide Web; 23–27 April 2018; Lyon, France. Geneva, Switzerland: International World Wide Web Conferences Steering Committee. pp. 539–548.
[33] Ou M, Cui P, Pei J, Zhang Z, Zhu W. Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 13–17 August 2016; San Francisco, CA, USA. New York, NY, USA: ACM. pp. 1105–1114.
[34] Rozemberczki B, Davies R, Sarkar R, Sutton C. Gemsec: Graph embedding with self clustering. arXiv preprint 2018, arXiv:1802.03997.
[35] Rozemberczki B, Sarkar R. Fast sequence based embedding with diffusion graphs. In: International Conference on Complex Networks; 11–13 December 2018; France. Cambridge, UK: Springer. pp. 99-107.
[36] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 24–27 August 2014; Washington, DC, USA. New York, NY, USA: ACM. pp. 701–710.
[37] Grover A, Leskovec J. node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 13–17 August 2016; San Francisco, CA, USA. New York, NY, USA: ACM. pp. 855-864.
[38] Sheikh N, Kefato Z, Montresor A. gat2vec: Representation learning for attributed graphs. Computing 2018; 9: 1-23.
[39] Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J. Distributed representations of words and phrases and their compositionality. Adv Neur In 2013; 23: 3111–3119.
[40] Cao S, Lu W, Xu Q. Grarep: Learning graph representations with global structural information. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management; 19–23 October 2015; Melbourne, Australia. New York, NY, USA: ACM. pp. 891–900.
[41] Liu Q, Li Z, Lui J, Cheng J. Powerwalk: Scalable personalized pagerank via random walks with vertex centric decomposition. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management; 24–26 October 2016; Indianapolis, IN, USA. New York, NY, USA: ACM. pp. 195–204.
[42] Pandhre S, Mittal H, Gupta M, Balasubramanian VN. Stwalk: learning trajectory representations in temporal graphs. In: Proceedings of the ACM India Joint International Conference on Data Science and Management of Data; 11–13 January 2018; Goa, India. New York, NY, USA: ACM. pp. 210–219.
[43] Mikolov T, Chen K, Corrado G, Dean J. Efficient estimation of word representations in vector space. arXiv preprint 2013, arXiv:1301.3781.
[44] Tran PV. Learning to make predictions on graphs with autoencoders. arXiv preprint 2018, arXiv:1802.08352.
[45] Wang Z, Ye X, Wang C, Wu Y, Wang C, Liang K. Rsdne: Exploring relaxed similarity and dissimilarity from completely-imbalanced labels for network embedding. Network 2018; 11: 475-482.
[46] Zhang M, Cui Z, Neumann M, Chen Y. An end-to-end deep learning architecture for graph classification. In: Proceedings of AAAI Conference on Artificial Inteligence; 2–7 February 2018; New Orleans, LA, USA: AAAI. pp. 531–538.
[47] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv preprint 2016, arXiv:1609.02907.
[48] Chen J, Ma T, Xiao C. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint 2018, arXiv:1801.10247.
[49] Donnat C, Zitnik M, Hallac D, Leskovec J. Spectral graph wavelets for structural role similarity in networks. arXiv preprint 2017, arXiv:1710.10321.
[50] Perozzi B, Kulkarni V, Chen H, Skiena S. Don’t walk, skip!: online learning of multi-scale network embeddings. In: Proceedings of the 2017 ACM International Conference on Advances in Social Networks Analysis and Mining; 1–3 August 2017; Sydney, Australia. New York, NY, USA: ACM. pp. 258–265.
[51] Desa C, Re C, Gu A, Sala F. Representation tradeoffs for hyperbolic embeddings. arXiv preprint 2018, arXiv:1804.03329.
[52] Goodreau SM. Advances in exponential random graph (p*) models applied to a large social network. Soc Networks 2007; 31: 231–248.
[53] Hoff PD, Raftery AE, Handcock MS. Latent space approaches to social network analysis. J Am Stat Assoc 2002; 64: 1090–1098.
[54] Snijders TAB. Longitudinal methods of network analysis. Enc Com Sys Sci 2009; 24: 5998–6013.
[55] Hoff PD. Dyadic data analysis with amen. arXiv preprint 2015, arXiv:1506.08237.
[56] Denny M. Social Network Analysis. Amherst, MA, USA: Academic Press, 2014.
[57] Denny M. Intermediate Social Network Theory. Amherst, MA, USA: Academic Press, 2015.
[58] Balasubramanian M, Schwartz EL. The isomap algorithm and topological stability. Science 2002; 295: 7.
[59] Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science 2000; 290: 2323–2326.
[60] Snijders TAB, Block P, Stadtfeld C. Forms of dependence: comparing SAOMs and ERGMs from basic principles. Sociol Method Res 2016; 43: 672–680.
[61] Hric D, Fortunato S. Community detection in networks: a user guide. Phys Rep 2016; 659: 1–44.
[62] Spenkuch J, Cicala S, Fryer RG. Self-selection and comparative advantage in social interactions. J Eur Econ Assoc 2017; 16: 1-44.