Communities and hierarchical structures in dynamic social networks: analysis and visualization | Social Network Analysis and Mining
Skip to main content
Springer Nature Link
Log in

Communities and hierarchical structures in dynamic social networks: analysis and visualization

  • Original Article
  • Published:
Social Network Analysis and Mining Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Detection of community structures in social networks has attracted lots of attention in the domain of sociology and behavioral sciences. Social networks also exhibit dynamic nature as these networks change continuously with the passage of time. Social networks might also present a hierarchical structure led by individuals who play important roles in a society such as managers and decision makers. Detection and visualization of these networks that are changing over time is a challenging problem where communities change as a function of events taking place in the society and the role people play in it. In this paper, we address these issues by presenting a system to analyze dynamic social networks. The proposed system is based on dynamic graph discretization and graph clustering. The system allows detection of major structural changes taking place in social communities over time and reveals hierarchies by identifying influential people in social networks. We use two different data sets for the empirical evaluation and observe that our system helps to discover interesting facts about the social and hierarchical structures present in these social networks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1
Fig. 3
Algorithm 2
Fig. 4
Fig. 5

Similar content being viewed by others

References

  • Adler RM (2007) A dynamic social network software platform for counter-terrorism decision support. In: ISI, IEEE, pp 47–54

  • Aggarwal CC, Han J, Wang J, Yu PS (2003) A framework for clustering evolving data streams. In: VLDB, pp 81–92

  • Auber D, Chiricota Y, Jourdan F, Melançon G (2003) Multiscale visualization of small-world networks. In: North SC, Munzner T (eds) Proceedings of IEEE information visualization symposium, Seattle, USA, IEEE Computer Press, pp 75–81

  • Barabasi AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512

    Article  MathSciNet  Google Scholar 

  • Baur M, Benkert M, Brandes U, Cornelsen S, Gaertler M, Kpf B, Lerner J, Wagner D (2002) Visone—software for visual social network analysis. In: Proceedings of the 9th International Symposium on Graph Drawing (GD '01), LNCS 2265, Springer, pp 463–464

  • Bender-deMoll S, McFarland DA (2006) The art and science of dynamic network visualization. J Soc Struct 7:2

    Google Scholar 

  • Berkhin P (2002) Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose

  • Bilgic M, Licamele L, Getoor L, Shneiderman B (2005) D-dupe: an interactive tool for entity resolution in social networks. In: Graph Drawing, pp 505–507

  • Bourqui R, Gilbert F, Simonetto P, Zaidi F, Sharan U, Jourdan F (2009) Detecting structural changes and command hierarchies in dynamic social networks. In: International Conference on Advances in Social Network Analysis and Mining, Los Alamitos, CA, USA. IEEE Computer Society, pp 83–88

  • Bourqui R, Simonetto P, Jourdan F (2009) A stable decomposition algorithm for dynamical social network analysis. Advances in Knowledge Discovery and Management, Studies in Computational Intelligence. Springer

  • Brohe S, van Helden J (2006) Evaluation of clustering algorithms for protein-protein interactionnetworks. BMC Bioinformatics 7(1):488

    Article  Google Scholar 

  • Buchheim C, Jünger M, Leipert S (2002) Improving walker’s algorithm to run in linear time. In: GD ’02: Revised Papers from the 10th International Symposium on Graph Drawing, London, UK. Springer, pp 344–353

  • Chakrabarti S, Dom B, Indyk P (1998) Enhanced hypertext categorization using hyperlinks. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp 307–318, 1998

  • Coleman JS (1964) An introduction to mathematical sociology. Collier-Macmillan, London

    Google Scholar 

  • Diesner J, Frantz TL, Carley KM (2005) Communication networks from the enron email corpus “it’s always about the people. enron is no different”. In: Comput Math Organ Theory, vol 11. Kluwer Academic Publishers, Hingham

  • Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 57–66

  • Eubank S, Guclu H, Kumar V, Marathe M, Srinivasan A, Toroczkai Z, Wang N (2004) Modelling disease outbreaks in realistic urban social networks. Nature 429:180184

    Article  Google Scholar 

  • Freeman L (2000) Visualizing social networks. J Soc Struct 1(1)

  • Freeman LC (2004) The Development of social network analysis: a study in the sociology of science. Empirical Press

  • Gajer P, Kobourov SG (2000) GRIP: graph drawing with Intelligent placement. In: Proceedings on Graph Drawing 2000 (GD’00), pp 222–228

  • Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci USA 99:8271–8276

    Article  MathSciNet  Google Scholar 

  • Gloor PA, Laubacher R, Zhao Y, Dynes SB (2004) Temporal visualization and analysis of social networks. In: NAACSOS Conference, June 27–29, Pittsburgh, PA. North American Association for Computational Social and Organizational Science

  • Hachul S, Junger M (2004) Drawing large graphs with a potential-fieldbased multilevel algorithm. vol 3383, pp 285–295

  • Heer J, Boyd D (2005) Vizster: visualizing online social networks. In: INFOVIS ’05: Proceedings of the 2005 IEEE Symposium on Information Visualization, Washington, DC, USA. IEEE Computer Society

  • Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3):264–323

    Article  Google Scholar 

  • Jankun-Kelly T, Ma K-L (2003) Moiregraphs: Radial focus+context visualization and nteraction for graphs with visual nodes. In: Munzner T and North S (eds) Proceedings of the 2003 IEEE Symposium on Information Visualization, IEEE Computer Society TCVG, IEEE Computer Society Press, pp 59–66

  • Kalnis P, Mamoulis N, Bakiras S (2005) On discovering moving clusters in spatio-temporal data. In: SSTD, pp 364–381

  • Kang H, Getoor L, Singh L (2007) Visual analysis of dynamic group membership in temporal social networks. SIGKDD Explor Newsl 9(2):13–21

    Article  Google Scholar 

  • Kretzschmar M, Morris M (1996) Measures of concurrency in networks and the spread of infectious disease. Math Biosci 133:165195

    Article  Google Scholar 

  • Kruskal J.B (1956) On the shortest spanning subtree and the traveling salesman problem. In: Proceedings of the American Mathematical Society, pp 48–50

  • Latora V, Marchiori M (2004) How Science of complex networks can help in developing strategy against Terrorism. Chaos Solitons and Fractals 20:69–75

    Article  MATH  Google Scholar 

  • Maeno Y, Ohsawa Y (2009) Analysing covert social network foundation behind terrorism disaster. Int J Serv Sci 2:125–141

    Article  Google Scholar 

  • Martinez V, Simari G, Silva A, Subrahmanian VS (2008) The soma terror organization portal (STOP): social network and analytic tools for the real-time analysis of terror groups. In: First International Workshop on Social Computing, Behavioral Modeling and Prediction

  • Memon N, Hicks DL, Larsen HL (2007) How investigative data mining can help intelligence agencies to discover dependence of nodes in terrorist networks. In: ADMA ’07: Proceedings of the 3rd international conference on advanced data mining and applications, pp 430–441. Springer

  • Memon N, Hicks DL, Larsen HL, Uqaili MA (2007) Understanding the structure of terrorist networks. Int J Bus Intell Data Min 2:401–425

    Article  Google Scholar 

  • Memon N, Larsen HL (2006) Practical approaches for analysis, visualization and destabilizing terrorist networks. In: ARES 06: Proceedings of the First International Conference on Availability, Reliability and Security. IEEE Computer Society, pp 906–913

  • Moody J, Mcfarland D, Benderdemoll S (2005) Dynamic network visualization. American Journal of Sociology 110(4):1206–1241

    Article  Google Scholar 

  • Newman ME (2001) Scientific collaboration networks. i. network construction and fundamental results. Phys Rev E Stat Nonlin Soft Matter Phys 64(1 Pt 2)

  • Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys 69(2 Pt 2)

  • Rapoport A, Horvath WJ (1961) A study of a large sociogram. Behavioral Science 6(4):279–291

    Article  Google Scholar 

  • Sarkar P, Moore AW (2005) Dynamic social network analysis using latent space models. SIGKDD Explor Newsl 7(2):31–40

    Article  Google Scholar 

  • Schaeffer SE (2007) Graph clustering. Comput Sci Rev 1(1):27–64

    Article  MathSciNet  Google Scholar 

  • Scott JP (2000) Social network analysis: a handbook. SAGE Publications, Newbury

  • Shen Z, Ma K-L, Eliassi-Rad T (2006) Visual analysis of large heterogeneous social networks by semantic and structural abstraction. IEEE Trans Vis Comput Graphics 12(6):1427–1439

    Article  Google Scholar 

  • Tryon RC (1939) Cluster analysis. Edwards Brothers, Ann Arbor

    Google Scholar 

  • Wasserman S, Faust K (1995) Social network analysis: methods and applications (structural analysis in the social sciences). Cambridge University Press, Cambridge

  • Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442

    Article  Google Scholar 

  • Yang CC, Ng TD (2007) Terrorism and crime related weblog social network: link, content analysis and information visualization. In: ISI, IEEE, pp 55–58

Download references

Author information

Authors and Affiliations

  1. CNRS UMR5800 LaBRI and INRIA Bordeaux-Sud Ouest, Talence, France

    Frédéric Gilbert, Paolo Simonetto, Faraz Zaidi & Romain Bourqui

  2. INRA, UMR1089, Toulouse, France

    Fabien Jourdan

Authors
  1. Frédéric Gilbert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paolo Simonetto
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Faraz Zaidi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Fabien Jourdan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Romain Bourqui
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Frédéric Gilbert.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gilbert, F., Simonetto, P., Zaidi, F. et al. Communities and hierarchical structures in dynamic social networks: analysis and visualization. Soc. Netw. Anal. Min. 1, 83–95 (2011). https://doi.org/10.1007/s13278-010-0002-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13278-010-0002-8

Keywords

Search

Navigation