Madhav CHANDANE, Pranav NERURKAR, Sunil BHIRUD

Understanding attribute and social circle correlation in social networks

Social circles, groups, lists, etc. are functionalities that allow users of online social network (OSN) platformsto manually organize their social media contacts. However, this facility provided by OSNs has not received appreciation from users due to the tedious nature of the task of organizing the ones that are only contacted periodically. In view of the numerous benefits of this functionality, it may be advantageous to investigate measures that lead to enhancements in its efficacy by allowing for automatic creation of customized groups of users (social circles, groups, lists, etc). The field of study for this purpose, i.e. creating coarse-grained descriptions from data, consists of two families of techniques, community discovery and clustering. These approaches are infeasible for the purpose of automation of social circle creation as they fail on social networks. A reason for this failure could be lack of knowledge of the global structure of the social network or the sparsity that exists in data from social networking websites. As individuals do in real life, OSN clients dependably attempt to broaden their groups of contacts in order to fulfill different social demands. This means that ‘homophily’ would exist among OSN users and prove useful in the task of social circle detection. Based on this intuition, the current inquiry is focused on understanding ‘homophily’ and its role in the process of social circle formation. Extensive experiments are performed on egocentric networks (ego is user, alters are friends) extracted from prominent OSNs like Facebook, Twitter, and Google+. The results of these experiments are used to propose a unified framework: feature extraction for social circles discovery (FESC). FESC detects social circles by jointly modeling ego-nettopology and attributes of alters. The performance of FESC is compared with standard benchmark frameworks using metrics like edit distance, modularity, and running time to highlight its efficacy.

PDF

___

[1] Chandane M, Bhirud S, Nerurkar P, Shirke A. A novel heuristic for evolutionary clustering. Procedia Comput Sci 2018; 125: 780–789.
[2] Liu H, Lin Y, Sangaiah AK, Zhang S, Li X. A privacy-preserving friend recommendation scheme in online social networks. Sustain Cities Soc 2018; 38: 275-285.
[3] Li H, Jiang Q, Gao S, Ma X, Ma J. Armor: A trust-based privacy-preserving framework for decentralized friend recommendation in online social networks. Future Gener Comp Sy 2018; 79: 82–94.
[4] Akoglu L, Perozzi B. Discovering communities and anomalies in attributed graphs: Interactive visual exploration and summarization. ACM T Knowl Discov D 2018; 12: 24-40.
[5] Sood K, Cui L, Pham VV, Yu S. Privacy issues in social networks and analysis: a comprehensive survey. IET Netw 2017; 7: 74-84.
[6] Zhao G, Mei T, Qian X, Feng H. Personalized recommendation combining user interest and social circle. IEEE T Knowl Data En 2014; 26: 1763–1777.
[7] Kosinski M, Stillwell D, Mo F, Zhou J. Usage patterns and social circles on Facebook among elderly people with diverse personality traits. Educ Gerontol 2018; 44: 265–275.
[8] Leskovec J, Yang J, McAuley J. Community detection in networks with node attributes. In: 13th International Conference on Data Mining; 7–10 December 2013; Dallas, TX, USA. pp. 1151–1156.
[9] Leskovec J, Yang J. Overlapping community detection at scale: a nonnegative matrix factorization approach. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining; 4–8 February 2013; Rome, Italy. New York, NY, USA: ACM. pp. 587–596.
[10] Alaa AM, Van der Schaar M, Ahuja K. A micro-foundation of social capital in evolving social networks. IEEE T Netw Sci Engg 2018; 5: 14–31.
[11] Tang J, Dong Y, Chawla NV. User modeling on demographic attributes in big mobile social networks. ACM T Inform Syst 2017; 35: 35-67.
[12] Chandane M, Bhirud S, Nerurkar P, Shirke A. Empirical analysis of data clustering algorithms. Procedia Comput Sci 2018; 125: 770–779.
[13] Li X, Luo B, Huan J, Lan C, Yang Y. Learning social circles in ego-networks based on multi-view network structure. IEEE T Knowl Data Eng 2017; 29: 1681-1694.
[14] Zhang C, Zimmermann R, Hong R, Zhang L. Flickr circles: aesthetic tendency discovery by multi-view regularized topic modeling. IEEE T Multimedia 2016; 18: 1555–1567.
[15] Chen Z, Xu M, Mei T, Lu D, Sang J. Who are your “real” friends: analyzing and distinguishing between offline and online friendships from social multimedia data. IEEE T Multimedia 2017; 19: 1299–1313.
[16] 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.
[17] 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.
[18] Jalili M, Perc M. Information cascades in complex networks. J Compl Netw 2017; 5: 665–693.
[19] Wang Z, Yamir M, Stefano B, Perc M. Vaccination and epidemics in networked populations—-an introduction. Chaos Soliton Fract 2017; 103: 177-183.
[20] 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.
[21] Martinčić-Ipšić S, Močibob E, Perc M. Link prediction on Twitter. PLoS One 2017; 12: e0181079.
[22] Nickel M, Kiela D. Poincare embeddings for learning hierarchical representations. Adv Neur In 2017; 31: 6338–6347.
[23] Perc M, Jordan JJ, Rand DG, Wang Z, Boccaletti S, Szolnoki A. Statistical physics of human cooperation. Phys Rep 2017; 687: 1-51.
[24] Ribeiro HV, Alves LG, Martins AF, Lenzi EK, Perc M. The dynamical structure of political corruption networks. arXiv preprint. arXiv: 1801.01869.
[25] Zitnik M, Agrawal M, Leskovec J. Modeling polypharmacy side effects with graph convolutional networks. arXiv preprint. arXiv: 1802.00543.
[26] Zitnik M, Leskovec J. Predicting multicellular function through multi-layer tissue networks. Bioinformatics 2017, 33: 190–198.
[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: ACM. pp. 633–641.
[30] Liao L, He X, Zhang H, Chua TS. Attributed social network embedding. arXiv preprint. 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. 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. 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] Yang Z, Cohen WW, Salakhutdinov R. Revisiting semi-supervised learning with graph embeddings. arXiv preprint. arXiv: 1603.08861.
[37] 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.
[38] 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.
[39] Sheikh N, Kefato Z, Montresor A. gat2vec: representation learning for attributed graphs. Computing 2018; 9: 1-23.
[40] 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.
[41] 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.
[42] 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.
[43] 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.
[44] Mikolov T, Chen K, Corrado G, Dean J. Efficient estimation of word representations in vector space. arXiv preprint. arXiv: 1301.3781.
[45] Tran PV. Learning to make predictions on graphs with autoencoders. arXiv preprint. arXiv: 1802.08352.
[46] 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.
[47] 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.
[48] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv preprint. arXiv:1609.02907.
[49] Chen J, Ma T, Xiao C. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint. arXiv: 1801.10247.
[50] Donnat C, Zitnik M, Hallac D, Leskovec J. Spectral graph wavelets for structural role similarity in networks. arXiv preprint. arXiv: 1710.10321.
[51] Wu L, Fisch A, Chopra S, Adams K, Bordes A, Weston J. Starspace: Embed all the things! arXiv preprint. arXiv: 1709.03856.
[52] 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.
53] Desa C, Re C, Gu A, Sala F. Representation tradeoffs for hyperbolic embeddings. arXiv preprint. arXiv: 1804.03329.
[54] Goodreau SM. Advances in exponential random graph (p*) models applied to a large social network. Soc Networks 2007; 31: 231–248.
[55] Hoff PD, Raftery AE, Handcock MS. Latent space approaches to social network analysis. J Am Stat Assoc 2002; 64: 1090–1098.
[56] Snijders TAB. Longitudinal methods of network analysis. Enc Com Sys Sci 2009; 24: 5998–6013.
[57] Hoff PD. Dyadic data analysis with amen. arXiv preprint. arXiv: 1506.08237.
[58] Denny M. Social Network Analysis. Amherst, MA, USA: Academic Press, 2014.
[59] Denny M. Intermediate Social Network Theory. Amherst, MA, USA: Academic Press, 2015.
[60] Balasubramanian M, Schwartz EL. The isomap algorithm and topological stability. Science 2002; 295: 7.
[61] Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science 2000; 290: 2323–2326.
[62] Leskovec J, Yang J, McAuley J. Detecting cohesive and 2-mode communities indirected and undirected networks. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining; 24–28 February 2014; New York, NY, USA: ACM. pp. 323–332.
[63] Singh M, Murukannaiah P. Platys social: Relating shared places and private social circles. IEEE Internet Comput 2012; 16: 53–59.
[64] Robardet C, Boulicaut JF, Prado A, Plantevit M. Mining graph topological patterns: finding covariations among vertex descriptors. IEEE T Knowl Data En 2013; 25: 2090–2104.