Skip to main content
Top

2014 | OriginalPaper | Chapter

Voronoi Diagram-Based Geometric Approach for Social Network Analysis

Authors : Subu Surendran, D. Chitraprasad, M. R. Kaimal

Published in: Computational Intelligence, Cyber Security and Computational Models

Publisher: Springer India

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Social network analysis is aimed at analyzing relationships between social network users. Such analysis aims at finding community detection, that is, group of closest people in a network. Usually, graph clustering techniques are used to identify groups. Here, we propose a computational geometric approach to analyze social network. A Voronoi diagram-based clustering algorithm is employed over embedded dataset in the Euclidean vector space to identify groups. Structure-preserving embedding technique is used to embed the social network dataset and learns a low-rank kernel matrix by means of a semi-definite program with linear constraints that captures the connectivity structure of the input graph.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference I-Hsien Ting, “Web Mining Techniques for On-line Social Networks Analysis”. Fifth IEEE international conference service systems and service management, 2008, pp. 1–5. I-Hsien Ting, “Web Mining Techniques for On-line Social Networks Analysis”. Fifth IEEE international conference service systems and service management, 2008, pp. 1–5.
2.
go back to reference Brandes, U., Gaertler, M., and Wagner, D. 2007. Engineering graph clustering: Models and experimental evaluation. Journal of Experimental Algorithmics (JEA).Vol.12, Article 1.1 (2008). Brandes, U., Gaertler, M., and Wagner, D. 2007. Engineering graph clustering: Models and experimental evaluation. Journal of Experimental Algorithmics (JEA).Vol.12, Article 1.1 (2008).
3.
go back to reference Newman, M. E. J. “Fast algorithm for detecting community structure in networks”, Physical Review -Series E, Vol 69; Part 6; Part 2, pages 066133 (2004) [5 pages]. Newman, M. E. J. “Fast algorithm for detecting community structure in networks”, Physical Review -Series E, Vol 69; Part 6; Part 2, pages 066133 (2004) [5 pages].
4.
go back to reference Vempala S., Kannan R., and Vetta A., “On clusterings good, bad and spectral”, In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS00). pp. 367–378. Vempala S., Kannan R., and Vetta A., “On clusterings good, bad and spectral”, In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS00). pp. 367–378.
5.
go back to reference M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks”. Physical Review -Series E Vol. 69, pages 026113 (2004) [15 pages]. M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks”. Physical Review -Series E Vol. 69, pages 026113 (2004) [15 pages].
6.
go back to reference Charu C Aggarwal, Haixun Wang, “Managing and Mining Graph Data”, Advances in Database Systems, Springer Science + Business Media, Chapter 16, pp. 487–513, 2010. Charu C Aggarwal, Haixun Wang, “Managing and Mining Graph Data”, Advances in Database Systems, Springer Science + Business Media, Chapter 16, pp. 487–513, 2010.
7.
go back to reference Aaron Clauset, M. E. J. Newman, and Cristopher Moore, “Finding community structure in very large networks”. Phys. Rev. E Vol. 70, 066111. (2004) [6 pages]. Aaron Clauset, M. E. J. Newman, and Cristopher Moore, “Finding community structure in very large networks”. Phys. Rev. E Vol. 70, 066111. (2004) [6 pages].
8.
go back to reference MEJ Newman, “Power laws, Pareto distributions and Zipf’s law”. Contemporary Physics 46:5, 323–351, 2005. MEJ Newman, “Power laws, Pareto distributions and Zipf’s law”. Contemporary Physics 46:5, 323–351, 2005.
9.
go back to reference J.Travers and S.Milgram, “An experimental study of the small world problem”. Sociometry, 32(4):425-443, 1969. J.Travers and S.Milgram, “An experimental study of the small world problem”. Sociometry, 32(4):425-443, 1969.
10.
go back to reference B. W. Kernighan and S. Lin “An efficient heuristic procedure for partitioning graphs”, Bell System Technical Journal, vol. 49, pp. 291–307 1970. B. W. Kernighan and S. Lin “An efficient heuristic procedure for partitioning graphs”, Bell System Technical Journal, vol. 49, pp. 291–307 1970.
11.
go back to reference Earl R. Barnes, “An Algorithm for Partitioning the Nodes of a Graph”, SIAM. J. on Algebraic and Discrete Methods, 3(4), 541550,1982. Earl R. Barnes, “An Algorithm for Partitioning the Nodes of a Graph”, SIAM. J. on Algebraic and Discrete Methods, 3(4), 541550,1982.
12.
go back to reference Ford L. R., and Fulkerson D. R., “Maximal flow through a network”, Can. J. Math 8, 399–404, 1956. Ford L. R., and Fulkerson D. R., “Maximal flow through a network”, Can. J. Math 8, 399–404, 1956.
13.
go back to reference M. E. J. Newman, “Modularity and community structure in networks”, Proceedings of National Academy of Sciences of the USA, Vol. 103 no. 23 pp. 8577–8582, 2006. M. E. J. Newman, “Modularity and community structure in networks”, Proceedings of National Academy of Sciences of the USA, Vol. 103 no. 23 pp. 8577–8582, 2006.
14.
go back to reference Rattigan, M. J., M. Maier, and D. Jensen, “Graph clustering with network structure indices”, ICML’07 Proceedings of the 24th international conference on Machine learning, (ACM, New York, NY, USA), pp. 783–790, 2007. Rattigan, M. J., M. Maier, and D. Jensen, “Graph clustering with network structure indices”, ICML’07 Proceedings of the 24th international conference on Machine learning, (ACM, New York, NY, USA), pp. 783–790, 2007.
16.
go back to reference Van Dongen, S. M., “Graph Clustering by Flow Simulation”. Ph.D. thesis, University of Utrecht, 2000. Van Dongen, S. M., “Graph Clustering by Flow Simulation”. Ph.D. thesis, University of Utrecht, 2000.
17.
go back to reference David Harel, Yehuda Koren, On clustering using random walks. In Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer S. Lecture Notes in Computer Science, vol. 2245. Springer-Verlag, New York. 1841, 2001. David Harel, Yehuda Koren, On clustering using random walks. In Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer S. Lecture Notes in Computer Science, vol. 2245. Springer-Verlag, New York. 1841, 2001.
18.
go back to reference Preparata F. P., M. I. Shamos, “Computational Geometry-An Introduction”, Springer-Verlag, August 1985. Preparata F. P., M. I. Shamos, “Computational Geometry-An Introduction”, Springer-Verlag, August 1985.
19.
go back to reference Blake Shaw, Tony Jebara, “Structure Preserving Embedding”, Proceedings of 26th International Conference on Machine Learning, Montreal, Canada, 2009. Blake Shaw, Tony Jebara, “Structure Preserving Embedding”, Proceedings of 26th International Conference on Machine Learning, Montreal, Canada, 2009.
20.
go back to reference Andrea Lancichinetti, Santo Fortunato, “Community detection algorithms: A comparative analysis”, Physical Review E, vol. 80, Issue 5, id. 056117, 2009. Andrea Lancichinetti, Santo Fortunato, “Community detection algorithms: A comparative analysis”, Physical Review E, vol. 80, Issue 5, id. 056117, 2009.
21.
go back to reference Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi, “Benchmark graphs for testing community detection algorithms”, Physical Review E, 78, 046110, 2008. Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi, “Benchmark graphs for testing community detection algorithms”, Physical Review E, 78, 046110, 2008.
23.
go back to reference Gary Flake, Steve Lawrence, C. Lee Giles, Frans Coetzee, “Self-Organization and Identification of Web Communities”, IEEE Computer, 35(3), 66–71, 2002. Gary Flake, Steve Lawrence, C. Lee Giles, Frans Coetzee, “Self-Organization and Identification of Web Communities”, IEEE Computer, 35(3), 66–71, 2002.
24.
go back to reference W. W. Zachary, “An information flow model for conflict and fission in small groups”, Journal of Anthropological Research 33, 452–473 (1977). W. W. Zachary, “An information flow model for conflict and fission in small groups”, Journal of Anthropological Research 33, 452–473 (1977).
Metadata
Title
Voronoi Diagram-Based Geometric Approach for Social Network Analysis
Authors
Subu Surendran
D. Chitraprasad
M. R. Kaimal
Copyright Year
2014
Publisher
Springer India
DOI
https://doi.org/10.1007/978-81-322-1680-3_39

Premium Partner