nach oben

Social Network Analysis and Mining

Erschienen in:

01.04.2011 | Original Article

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

verfasst von: Frédéric Gilbert, Paolo Simonetto, Faraz Zaidi, Fabien Jourdan, Romain Bourqui

Erschienen in: Social Network Analysis and Mining | Ausgabe 2/2011

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation

Nächster Artikel Market basket analysis with networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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–512CrossRefMathSciNet

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

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):488CrossRef

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

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:180184CrossRef

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–8276CrossRefMathSciNet

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–323CrossRef

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–21CrossRef

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

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–75CrossRefMATH

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

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–425CrossRef

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–1241CrossRef

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–291CrossRef

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

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

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–1439CrossRef

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

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–442CrossRef

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

Titel: Communities and hierarchical structures in dynamic social networks: analysis and visualization
verfasst von: Frédéric Gilbert
Paolo Simonetto
Faraz Zaidi
Fabien Jourdan
Romain Bourqui
Publikationsdatum: 01.04.2011
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 2/2011
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-010-0002-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2011

Seeing similarity in the face of difference: enabling comparison of online production systems

Understanding actor loyalty to event-based groups in affiliation networks

Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation

Market basket analysis with networks

Introduction to the second issue of Social Network Analysis and Mining journal: scientific computing for social network analysis and dynamicity

Premium Partner