Group-Level Analysis and Visualization of Social Networks | SpringerLink
Skip to main content
Springer Nature Link
Log in

Group-Level Analysis and Visualization of Social Networks

  • Chapter
Algorithmics of Large and Complex Networks

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5515))

Abstract

Social network analysis investigates the structure of relations amongst social actors. A general approach to detect patterns of interaction and to filter out irregularities is to classify actors into groups and to analyze the relational structure between and within the various classes. The first part of this paper presents methods to define and compute structural network positions, i. e., classes of actors dependent on the network structure. In the second part we present techniques to visualize a network together with a given assignment of actors into groups, where specific emphasis is given to the simultaneous visualization of micro and macro structure.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Achlioptas, D., Fiat, A., Karlin, A., McSherry, F.: Web Search Via Hub Synthesis. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2001), pp. 500–509 (2001)

    Google Scholar 

  2. Alon, N., Kahale, N.: A Spectral Technique for Coloring Random 3-Colorable Graphs. SIAM Journal on Computation 26, 1733–1748 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  3. Archambault, D., Munzner, T., Auber, D.: TopoLayout: Multi-Level Graph Layout by Topological Features. IEEE Transactions on Visualization and Computer Graphics 13(2), 305–317 (2007)

    Article  Google Scholar 

  4. Azar, Y., Fiat, A., Karlin, A., McSherry, F., Saia, J.: Spectral Analysis of Data. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 619–626 (2001)

    Google Scholar 

  5. Bachmaier, C.: A Radial Adaptation of the Sugiyama Framework for Visualizing Hierarchical Information. IEEE Transactions on Visualization and Computer Graphics 13(3), 585–594 (2007)

    Article  Google Scholar 

  6. Balzer, M., Deussen, O.: Level-of-Detail Visualization of Clustered Graph Layouts. In: Asia-Pacific Symposium on Visualisation 2007, APVIS 2007 (2007)

    Google Scholar 

  7. Batagelj, V., Doreian, P., Ferligoj, A.: An Optimizational Approach to Regular Equivalence. Social Networks 14, 121–135 (1992)

    Article  Google Scholar 

  8. Baur, M., Brandes, U.: Crossing Reduction in Circular Layouts. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 332–343. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  9. Borgatti, S.P., Everett, M.G.: Notions of Position in Social Network Analysis. Sociological Methodology 22, 1–35 (1992)

    Article  Google Scholar 

  10. Brandes, U.: On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2), 136–145 (2008)

    Article  Google Scholar 

  11. Brandes, U., Erlebach, T. (eds.): Network Analysis: Methodological Foundations. Springer, Heidelberg (2005)

    MATH  Google Scholar 

  12. Brandes, U., Fleischer, D., Lerner, J.: Summarizing Dynamic Bipolar Conflict Structures. IEEE Transactions on Visualization and Computer Graphics, special issue on Visual Analytics 12(6), 1486–1499 (2006)

    Article  Google Scholar 

  13. Brandes, U., Lerner, J.: Structural Similarity in Graphs. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 184–195. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  14. Brandes, U., Lerner, J.: Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 202–213. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  15. Brandes, U., Lerner, J.: Visualization of Conflict Networks. In: Kauffmann, M. (ed.) Building and Using Datasets on Armed Conflicts. NATO Science for Peace and Security Series E: Human and Societal Dynamics, vol. 36. IOS Press, Amsterdam (2008)

    Google Scholar 

  16. Coja-Oghlan, A.: A Spectral Heuristic for Bisecting Random Graphs. In: Proceeding of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 850–859 (2005)

    Google Scholar 

  17. Cox, T.F., Cox, M.A.A.: Multidimensional Scaling, 2nd edn. Monographs on Statistics and Applied Probability. Chapman & Hall/CRC, Boca Raton (2001)

    MATH  Google Scholar 

  18. Cvetković, D.M., Doob, M., Sachs, H.: Spectra of Graphs. Johann Ambrosius Barth Verlag (1995)

    Google Scholar 

  19. Doreian, P., Batagelj, V., Ferligoj, A.: Generalized Blockmodeling. Structural Analysis in the Social Sciences, vol. 25. Cambridge University Press, Cambridge (2005)

    MATH  Google Scholar 

  20. Duncan, C.A., Efrat, A., Kobourov, S.G., Wenk, C.: Drawing with Fat Edges. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 162–177. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  21. Eades, P., Kelly, D.: Heuristics for Reducing Crossings in 2-Layered Networks. Ars Combinatoria 21(A), 89–98 (1986)

    MathSciNet  MATH  Google Scholar 

  22. Everett, M.G., Borgatti, S.P.: Regular Equivalence: General Theory. Journal of Mathematical Sociology 18(1), 29–52 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  23. Fiala, J., Paulusma, D.: The Computational Complexity of the Role Assignment Problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 817–828. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  24. Fleischer, D.: Theory and Applications of the Laplacian. Ph.D thesis (2007)

    Google Scholar 

  25. Freeman, L.C.: Visualizing Social Networks. Journal of Social Structure 1(1) (2000)

    Google Scholar 

  26. Fruchterman, T.M.J., Reingold, E.M.: Graph Drawing by Force-Directed Placement. Software - Practice and Experience 21(11), 1129–1164 (1991)

    Article  Google Scholar 

  27. Gaertler, M.: Algorithmic Aspects of Clustering – Theory, Experimental Evaluation and Applications in Network Analysis and Visualization. Ph.D thesis, Universität Karlsruhe (TH), Fakultät für Informatik (2007)

    Google Scholar 

  28. Gansner, E.R., Koren, Y.: Improved Circular Layouts. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 386–398. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  29. Gansner, E.R., North, S.C.: Improved Force-Directed Layouts. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 364–373. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  30. Gkantsidis, C., Mihail, M., Zegura, E.W.: Spectral Analysis of Internet Topologies. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom), vol. 1, pp. 364–374. IEEE Computer Society Press, Los Alamitos (2003)

    Google Scholar 

  31. Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics. Springer, Heidelberg (2001)

    Book  MATH  Google Scholar 

  32. Golub, G.H., van Loan, C.F.: Matrix Computations. John Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  33. Harel, D., Koren, Y.: Drawing Graphs with Non-Uniform Vertices. In: Proceedings of the 6th Working Conference on Advanced Visual Interfaces (AVI 2002), pp. 157–166. ACM Press, New York (2002)

    Chapter  Google Scholar 

  34. Holten, D.: Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data. IEEE Transactions on Visualization and Computer Graphics 12(5), 741–748 (2006)

    Article  Google Scholar 

  35. Kannan, R., Vempala, S., Vetta, A.: On clusterings: Good, Bad and Spectral. Journal of the ACM 51(3), 497–515 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  36. Kaufmann, M., Wiese, R.: Maintaining the Mental Map for Circular Drawings. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 12–22. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  37. Krebs, V.E.: Visualizing Human Networks. Release 1.0, pp. 1–25 (1996)

    Google Scholar 

  38. Krempel, L.: Visualisierung komplexer Strukturen. Grundlagen der Darstellung mehrdimensionaler Netzwerke. Campus (2005)

    Google Scholar 

  39. Lerner, J.: Role Assignments. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 216–252. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  40. Lerner, J.: Structural Similarity of Vertices in Networks. Ph.D thesis (2007)

    Google Scholar 

  41. Lorrain, F., White, H.C.: Structural Equivalence of Individuals in Social Networks. Journal of Mathematical Sociology 1, 49–80 (1971)

    Article  Google Scholar 

  42. Luczkovich, J.J., Borgatti, S.P., Johnson, J.C., Everett, M.G.: Defining and Measuring Trophic Role Similarity in Food Webs Using Regular Equivalence. Journal of Theoretical Biology 220(3), 303–321 (2003)

    Article  MathSciNet  Google Scholar 

  43. Masuda, S., Kashiwabara, T., Nakajima, K., Fujisawa, T.: On the \(\mathcal{NP}\)-Completeness of a Computer Network Layout Problem. In: Proceedings of the 20th IEEE International Symposium on Circuits and Systems 1987, pp. 292–295. IEEE Computer Society, Los Alamitos (1987)

    Google Scholar 

  44. Matuszewski, C., Schönfeld, R., Molitor, P.: Using Sifting for k-Layer Straightline Crossing Minimization. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 217–224. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  45. McSherry, F.: Spectral Partitioning of Random Graphs. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2001), pp. 529–537 (2001)

    Google Scholar 

  46. Papadimitriou, C., Raghavan, P., Tamaki, H., Vempala, S.: Latent Semantic Indexing: A Probabilistic Analysis. Journal of Computer and System Sciences 61(2), 217–235 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  47. Rudell, R.: Dynamic Variable Ordering for Ordered Binary Decision Diagrams. In: Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design, pp. 42–47. IEEE Computer Society Press, Los Alamitos (1993)

    Google Scholar 

  48. Sailer, L.D.: Structural Equivalence: Meaning and Definition, Computation and Application. Social Networks 1, 73–90 (1978)

    Article  Google Scholar 

  49. Schrodt, P.A., Davis, S.G., Weddle, J.L.: Political Science: KEDS - A Program for the Machine Coding of Event Data. Social Science Computer Review 12(3), 561–588 (1994)

    Article  Google Scholar 

  50. Six, J.M., Tollis, I.G.: A Framework for User-Grouped Circular Drawings. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 135–146. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  51. Stewart, G.W., Sun, J.-G.: Matrix Perturbation Theory. Academic Press, London (1990)

    MATH  Google Scholar 

  52. Vempala, S., Wang, G.: A Spectral Algorithm for Learning Mixtures of Distributions. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2002 (2002)

    Google Scholar 

  53. Wang, X., Miyamoto, I.: Generating Customized Layouts. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 504–515. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  54. Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge (1994)

    Book  MATH  Google Scholar 

  55. White, D.R., Reitz, K.P.: Graph and Semigroup Homomorphisms on Networks of Relations. Social Networks 5, 193–234 (1983)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Informatics, Universität Karlsruhe (TH), KIT, Germany

    Michael Baur & Dorothea Wagner

  2. Department of Computer & Information Science, University of Konstanz, Germany

    Ulrik Brandes & Jürgen Lerner

Authors
  1. Michael Baur
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ulrik Brandes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jürgen Lerner
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dorothea Wagner
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer & Information Science, University of Konstanz, 78457, Konstanz, Germany

    Jürgen Lerner

  2. Institute of Theoretical Informatics, Technical University of Karlsruhe, 76128, Karlsruhe, Germany

    Dorothea Wagner

  3. Department of Biological Physics, Eötvös Lorand University, Pazmany P. Stny 1A, 1117, Budapest, Hungary

    Katharina A. Zweig

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Baur, M., Brandes, U., Lerner, J., Wagner, D. (2009). Group-Level Analysis and Visualization of Social Networks. In: Lerner, J., Wagner, D., Zweig, K.A. (eds) Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science, vol 5515. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02094-0_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02094-0_16

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02093-3

  • Online ISBN: 978-3-642-02094-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation