Advances in Network Clustering and Blockmodeling

Patrick Doreian, MA, is Professor Emeritus of Sociology and Statistics at the University of Pittsburgh and has a research position at the Faculty of Social Sciences at the University of Ljubljana. He has published over 150 articles in academic journals as well as nine books and numerous book chapters. His co-authored book Generalized Blockmodeling written with Vladimir Batagelj and Anuška Ferligoj received the Harrison White Outstanding Book Award in 2007. He is an honorary Senator of the University of Ljubljana, Slovenia. Vladimir Batagelj, PhD, is Professor Emeritus of Discrete and Computational Mathematics from the University of Ljubljana, Slovenia. He is Senior Researcher at the Department of Theoretical Computer Science of IMFM, Ljubljana, the Institute Andrej Marušic at University of Primorska, Koper, and NRU HSE International Laboratory for Applied Network Research, Moscow. He is a co-author of program Pajek for large network analysis and visualization. He is an elected member of the International Statistical Institute. With Patrick Doreian, Anuška Ferligoj and Nataša Kej??ar he co-authored the book Understanding Large Temporal Networks and Spatial Networks, Wiley, 2014. Anuška Ferligoj, PhD, is Professor of Statistics at the Faculty of Social Sciences at the University of Ljubljana and academic supervisor at the NRU HSE International Laboratory for Applied Network Research, Moscow. She is a member of the European Academy of Sociology. In 2010 she received the Doctor et Professor Honoris Causa at the Eötvös Loránd University, Budapest, Hungary.

• List of Contributors xv1 Introduction 1Patrick Doreian, Vladimir Batagelj, and Anuška Ferligoj1.1 On the Chapters 11.2 Looking Forward 92 Bibliometric Analyses of the Network Clustering Literature 11Vladimir Batagelj, Anuška Ferligoj, and Patrick Doreian2.1 Introduction 112.2 Data Collection and Cleaning 122.2.1 Most Cited/Citing Works 152.2.2 The Boundary Problem for Citation Networks 172.3 Analyses of the Citation Networks 192.3.1 Components 202.3.2 The CPM Path of the Main Citation Network 202.3.3 Key-Route Paths 202.3.4 Positioning Sets of Selected Works in a Citation Network 302.4 Link Islands in the Clustering Network Literature 352.4.1 Island 10: Community Detection and Blockmodeling 352.4.2 Island 7: Engineering Geology 362.4.3 Island 9: Geophysics 382.4.4 Island 2: Electromagnetic Fields and their Impact on Humans 382.4.5 Limitations and Extensions 402.5 Authors 412.5.1 Productivity Inside Research Groups 422.5.2 Collaboration 432.5.3 Citations Among Authors Contributing to the Network Partitioning Literature 452.5.4 Citations Among Journals 472.5.5 Bibliographic Coupling 502.5.6 Linking Through a Jaccard Network 582.6 Summary and Future Work 62Acknowledgements 63References 633 Clustering Approaches to Networks 65Vladimir Batagelj3.1 Introduction 653.2 Clustering 663.2.1 The Clustering Problem 663.2.2 Criterion Functions 673.2.3 Cluster-Error Function/Examples 723.2.4 The Complexity of the Clustering Problem 753.3 Approaches to Clustering 763.3.1 Local Optimization 763.3.2 Dynamic Programming 793.3.3 Hierarchical Methods 793.3.4 Adding Hierarchical Methods 833.3.5 The Leaders Method 843.4 Clustering Graphs and Networks 873.5 Clustering in Graphs and Networks 893.5.1 An Indirect Approach 893.5.2 A Direct Approach: Blockmodeling 903.5.3 Graph Theoretic Approaches 903.6 Agglomerative Method for Relational Constraints 903.6.1 Software Support 953.7 Some Examples 953.7.1 The US Geographical Data, 2016 953.7.2 Citations Among Authors from the Network Clustering Literature 983.8 Conclusion 102Acknowledgements 102References 1024 Different Approaches to Community Detection 105Martin Rosvall, Jean-Charles Delvenne, Michael T. Schaub, and Renaud Lambiotte4.1 Introduction 1054.2 Minimizing Constraint Violations: the Cut-based Perspective 1074.3 Maximizing Internal Density: the Clustering Perspective 1084.4 Identifying Structural Equivalence: the Stochastic Block Model Perspective 1104.5 Identifying Coarse-grained Descriptions: the Dynamical Perspective 1114.6 Discussion 1144.7 Conclusions 116Acknowledgements 116References 1165 Label Propagation for Clustering 121Lovro Šubelj5.1 Label Propagation Method 1215.1.1 Resolution of Label Ties 1235.1.2 Order of Label Propagation 1235.1.3 Label Equilibrium Criterium 1245.1.4 Algorithm and Complexity 1255.2 Label Propagation as Optimization 1275.3 Advances of Label Propagation 1285.3.1 Label Propagation Under Constraints 1295.3.2 Label Propagation with Preferences 1305.3.3 Method Stability and Complexity 1335.4 Extensions to Other Networks 1375.5 Alternative Types of Network Structures 1395.5.1 Overlapping Groups of Nodes 1395.5.2 Hierarchy of Groups of Nodes 1405.5.3 Structural Equivalence Groups 1425.6 Applications of Label Propagation 1465.7 Summary and Outlook 146References 1476 Blockmodeling of Valued Networks 151Carl Nordlund and Aleš Žiberna6.1 Introduction 1516.2 Valued Data Types 1536.3 Transformations 1546.3.1 Scaling Transformations 1556.3.2 Dichotomization 1576.3.3 Normalization Procedures 1576.3.4 Iterative Row-column Normalization 1586.3.5 Transaction-flow and Deviational Transformations 1596.4 Indirect Clustering Approaches 1606.4.1 Structural Equivalence: Indirect Metrics 1606.4.2 The CONCOR Algorithm 1616.4.3 Deviational Structural Equivalence: Indirect Approach 1626.4.4 Regular Equivalence: The REGE Algorithms 1626.4.5 Indirect Approaches: Finding Clusters, Interpreting Blocks 1636.5 Direct Approaches 1646.5.1 Generalized Blockmodeling 1646.5.2 Generalized Blockmodeling of Valued Networks 1656.5.3 Deviational Generalized Blockmodeling 1666.6 On the Selection of Suitable Approaches 1676.7 Examples 1686.7.1 EIES Friendship Data at Time 2 1686.7.2 Commodity Trade Within EU/EFTA 2010 1736.8 Conclusion 183Acknowledgements 185References 1857 Treating Missing Network Data Before Partitioning 189Anja Žnidaršič, Patrick Doreian, and Anuška Ferligoj7.1 Introduction 1897.2 Types of Missing Network Data 1907.2.1 Measurement Errors in Recorded (Or Reported) Ties 1907.2.2 Item Non-Response 1927.2.3 Actor Non-Response 1927.3 Treatments of Missing Data (Due to Actor Non-Response) 1937.3.1 Reconstruction 1947.3.2 Imputations of the Mean Values of Incoming Ties 1967.3.3 Imputations of the Modal Values of Incoming Ties 1967.3.4 Reconstruction and Imputations Based on Modal Values of Incoming Ties 1977.3.5 Imputations of the Total Mean 1977.3.6 Imputations of Median of the Three Nearest Neighbors based on Incoming Ties 1977.3.7 Null Tie Imputations 1987.3.8 Blockmodel Results for the Whole and Treated Networks 1987.4 A Study Design Examining the Impact of Non-Response Treatments on Clustering Results 2007.4.1 Some Features of Indirect and Direct Blockmodeling 2007.4.2 Design of the Simulation Study 2017.4.3 The Real Networks Used in the Simulation Studies 2017.5 Results 2027.5.1 Indirect Blockmodeling of Real Valued Networks 2027.5.2 Indirect Blockmodeling on Real Binary Networks 2107.5.3 Direct Blockmodeling of Binary Real Networks 2167.6 Conclusions 222Acknowledgements 223References 2238 Partitioning Signed Networks 225Vincent Traag, Patrick Doreian, and Andrej Mrvar8.1 Notation 2258.2 Structural Balance Theory 2268.2.1 Weak Structural Balance 2308.3 Partitioning 2328.3.1 Strong Structural Balance 2338.3.2 Weak Structural Balance 2378.3.3 Blockmodeling 2388.3.4 Community Detection 2398.4 Empirical Analysis 2428.5 Summary and Future Work 247References 2489 Partitioning Multimode Networks 251Martin G Everett and Stephen P Borgatti9.1 Introduction 2519.2 Two-Mode Partitioning 2529.3 Community Detection 2539.4 Dual Projection 2549.5 Signed Two-Mode Networks 2579.6 Spectral Methods 2589.7 Clustering 2619.8 More Complex Data 2629.9 Conclusion 263References 26310 Blockmodeling Linked Networks 267Aleš Žiberna10.1 Introduction 26710.2 Blockmodeling Linked Networks 26810.2.1 Separate Analysis 26910.2.2 A True Linked Blockmodeling Approach 26910.2.3 Weighting of Different Parts of a Linked Network 27010.3 Examples 27010.3.1 Co-authorship Network at Two Time-points 27010.3.2 A Multilevel Network of Participants at a Trade Fair for TV Programs 27710.4 Conclusion 284Acknowledgements 285References 28511 Bayesian Stochastic Blockmodeling 289Tiago P. Peixoto11.1 Introduction 28911.2 Structure Versus Randomness in Networks 29011.3 The Stochastic Blockmodel 29211.4 Bayesian Inference: The Posterior Probability of Partitions 29411.5 Microcanonical Models and the Minimum Description Length Principle 29811.6 The “Resolution Limit” Underfitting Problem and the Nested SBM 30011.7 Model Variations 30511.7.1 Model Selection 30611.7.2 Degree Correction 30611.7.3 Group Overlaps 31011.7.4 Further Model Extensions 31311.8 Efficient Inference Using Markov Chain Monte Carlo 31411.9 To Sample or To Optimize? 31711.10 Generalization and Prediction 32111.11 Fundamental Limits of Inference: The Detectability–Indetectability Phase Transition 32311.12 Conclusion 327References 32812 Structured Networks and Coarse-Grained Descriptions: A Dynamical Perspective 333Michael T. Schaub, Jean-Charles Delvenne, Renaud Lambiotte, and Mauricio Barahona12.1 Introduction 33312.2 Part I: Dynamics on and of Networks 33712.2.1 General Setup 33712.2.2 Consensus Dynamics 33812.2.3 Diffusion Processes and Random Walks 34012.3 Part II: The Influence of Graph Structure on Network Dynamics 34212.3.1 Time Scale Separation in Partitioned Networks 34212.3.2 Strictly Invariant Subspaces of the Network Dynamics and External Equitable Partitions 34512.3.3 Structural Balance: Consensus on Signed Networks and Polarized Opinion Dynamics 34812.4 Part III: Using Dynamical Processes to Reveal Network Structure 35112.4.1 A Generic Algorithmic Framework for Dynamics-Based Network Partitioning and Coarse Graining 35212.4.2 Extending the Framework by using other Measures 35412.5 Discussion 357Acknowledgements 358References 35813 Scientific Co-Authorship Networks 363Marjan Cugmas, Anuška Ferligoj, and Luka Kronegger13.1 Introduction 36313.2 Methods 36413.2.1 Blockmodeling 36513.2.2 Measuring the Obtained Blockmodels’ Stability 36513.3 The Data 36913.4 The Structure of Obtained Blockmodels 37013.5 Stability of the Obtained Blockmodel Structures 37813.5.1 Clustering of Scientific Disciplines According to Different Operationalizations of Core Stability 37813.5.2 Explaining the Stability of Cores 38213.6 Conclusions 384Acknowledgements 386References 38614 Conclusions and Directions for Future Work 389Patrick Doreian, Anuška Ferligoj, and Vladimir Batagelj14.1 Issues Raised within Chapters 39014.2 Linking Ideas Found in Different Chapters 39514.3 A Brief Summary and Conclusion 397References 397Topic Index 399Person Index 407