Graph Theoretic Approach to Social Network Analysis
Keywords:
Community Detection, Quality Function, Modularity, Transitivity Index.Abstract
In the last few years, there is a rapid growth of web and various social network sites which have enabled us to easily interconnect people all over the world in a shared platform. A social network is a social structure comprising individuals or organizations which hold dynamic ties between them. Social network can be visualized in terms of connected graph where individuals are represented by vertices or nodes and connections between individuals are represented by link or edges. The tendency of people based on their preferences, choices, likes or dislikes are associated with each other in a shared platform, which forms a virtual cluster or community. In this paper we generate a graph of communication network based on real life data collected from a social network site - Twitter. Several community detection algorithms are in place and our intention is to make a comparative study of these existing algorithms over our graph and detect the communities which cannot be viewed by mere observation.
References
- M. E Newman, Modularity and community structure in networks, Proceedings of the national academy of sciences, vol.103 (23), pp.8577-8582, 2006.
- D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature, vol.393, pp.440-442, 1998.
- L. A. N Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, Classes of small-world networks, Proceedings of the national academy of sciences,vol. 97 (21), pp.11149-11152, 2000.
- D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of inuence through a social network, In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146, 2003.
- R. T. Sparrowe, and R. C. Liden, Two routes to inuence: Integrating leader-member exchange and social network perspectives, Administrative Science Quarterly, vol.50 (4), pp.505-535, 2005.
- M. Girvan, and M. E. Newman, Community structure in social and biological networks, Proceedings of the national academy of sciences, vol.99 (12), pp.7821-7826, 2003.
- A.Clauset, C. R. Shalizi, and M. E. Newman, Power-law distributions in empirical data, SIAM review, vol. 51 (4), pp. 661-703, 2009.
- L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman, Search in power-law networks, Physical review E 64 (4), 2001.
- S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, Cambridge University Press, 1994.
- R. D.Luce and A. D. Perry, A method of matrix analysis of group structure, Psychometrika, vol.14 (2), pp.95-116, 1949.
- G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature, vol.435, pp. 814, 2005.
- L. Bomze, I. M., M. Budinich, P. M. Pardalos and M. Pelillo, Handbook of Combinatorial Optimization, Kluwer Academic Publishers, Norwell, pp. 1-74, 1999.
- P. Erdos, and Rnyi, On the evolution of random graphs, Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pp.17-61, 1960.
- M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69(2), 2004.
- U.N.Raghavan, R. Albert, S. Kumara,? Near linear time algorithm to detect community structures in large-scale networks, Physical Review E 76, 036106, 2007.
- P. Pons and M. Latapy, Computing communities in large networks using random walks, Journal of Graph Algorithms and Applications, vol. 10, no. 2, pp. 191?218, 2006.
- S. Fortunato, Community detection in graphs, Physics Reports, vol. 486,? pp.75?174, 2010.
Downloads
Published
Issue
Section
License
Copyright (c) IJSRST
This work is licensed under a Creative Commons Attribution 4.0 International License.
