List of Contributors xv
1 Introduction 1
Patrick Doreian, Vladimir Batagelj, and Anuška Ferligoj
1.1 On the Chapters 1
1.2 Looking Forward 9
2 Bibliometric Analyses of the Network Clustering Literature 11
Vladimir Batagelj, Anuška Ferligoj, and Patrick Doreian
2.1 Introduction 11
2.2 Data Collection and Cleaning 12
2.2.1 Most Cited/Citing Works 15
2.2.2 The Boundary Problem for Citation Networks 17
2.3 Analyses of the Citation Networks 19
2.3.1 Components 20
2.3.2 The CPM Path of the Main Citation Network 20
2.3.3 Key-Route Paths 20
2.3.4 Positioning Sets of Selected Works in a Citation Network 30
2.4 Link Islands in the Clustering Network Literature 35
2.4.1 Island 10: Community Detection and Blockmodeling 35
2.4.2 Island 7: Engineering Geology 36
2.4.3 Island 9: Geophysics 38
2.4.4 Island 2: Electromagnetic Fields and their Impact on Humans 38
2.4.5 Limitations and Extensions 40
2.5 Authors 41
2.5.1 Productivity Inside Research Groups 42
2.5.2 Collaboration 43
2.5.3 Citations Among Authors Contributing to the Network Partitioning Literature 45
2.5.4 Citations Among Journals 47
2.5.5 Bibliographic Coupling 50
2.5.6 Linking Through a Jaccard Network 58
2.6 Summary and Future Work 62
Acknowledgements 63
References 63
3 Clustering Approaches to Networks 65
Vladimir Batagelj
3.1 Introduction 65
3.2 Clustering 66
3.2.1 The Clustering Problem 66
3.2.2 Criterion Functions 67
3.2.3 Cluster-Error Function/Examples 72
3.2.4 The Complexity of the Clustering Problem 75
3.3 Approaches to Clustering 76
3.3.1 Local Optimization 76
3.3.2 Dynamic Programming 79
3.3.3 Hierarchical Methods 79
3.3.4 Adding Hierarchical Methods 83
3.3.5 The Leaders Method 84
3.4 Clustering Graphs and Networks 87
3.5 Clustering in Graphs and Networks 89
3.5.1 An Indirect Approach 89
3.5.2 A Direct Approach: Blockmodeling 90
3.5.3 Graph Theoretic Approaches 90
3.6 Agglomerative Method for Relational Constraints 90
3.6.1 Software Support 95
3.7 Some Examples 95
3.7.1 The US Geographical Data, 2016 95
3.7.2 Citations Among Authors from the Network Clustering Literature 98
3.8 Conclusion 102
Acknowledgements 102
References 102
4 Different Approaches to Community Detection 105
Martin Rosvall, Jean-Charles Delvenne, Michael T. Schaub, and Renaud Lambiotte
4.1 Introduction 105
4.2 Minimizing Constraint Violations: the Cut-based Perspective 107
4.3 Maximizing Internal Density: the Clustering Perspective 108
4.4 Identifying Structural Equivalence: the Stochastic Block Model Perspective 110
4.5 Identifying Coarse-grained Descriptions: the Dynamical Perspective 111
4.6 Discussion 114
4.7 Conclusions 116
Acknowledgements 116
References 116
5 Label Propagation for Clustering 121
Lovro Å ubelj
5.1 Label Propagation Method 121
5.1.1 Resolution of Label Ties 123
5.1.2 Order of Label Propagation 123
5.1.3 Label Equilibrium Criterium 124
5.1.4 Algorithm and Complexity 125
5.2 Label Propagation as Optimization 127
5.3 Advances of Label Propagation 128
5.3.1 Label Propagation Under Constraints 129
5.3.2 Label Propagation with Preferences 130
5.3.3 Method Stability and Complexity 133
5.4 Extensions to Other Networks 137
5.5 Alternative Types of Network Structures 139
5.5.1 Overlapping Groups of Nodes 139
5.5.2 Hierarchy of Groups of Nodes 140
5.5.3 Structural Equivalence Groups 142
5.6 Applications of Label Propagation 146
5.7 Summary and Outlook 146
References 147
6 Blockmodeling of Valued Networks 151
Carl Nordlund and Aleš iberna
6.1 Introduction 151
6.2 Valued Data Types 153
6.3 Transformations 154
6.3.1 Scaling Transformations 155
6.3.2 Dichotomization 157
6.3.3 Normalization Procedures 157
6.3.4 Iterative Row-column Normalization 158
6.3.5 Transaction-flow and Deviational Transformations 159
6.4 Indirect Clustering Approaches 160
6.4.1 Structural Equivalence: Indirect Metrics 160
6.4.2 The CONCOR Algorithm 161
6.4.3 Deviational Structural Equivalence: Indirect Approach 162
6.4.4 Regular Equivalence: The REGE Algorithms 162
6.4.5 Indirect Approaches: Finding Clusters, Interpreting Blocks 163
6.5 Direct Approaches 164
6.5.1 Generalized Blockmodeling 164
6.5.2 Generalized Blockmodeling of Valued Networks 165
6.5.3 Deviational Generalized Blockmodeling 166
6.6 On the Selection of Suitable Approaches 167
6.7 Examples 168
6.7.1 EIES Friendship Data at Time 2 168
6.7.2 Commodity Trade Within EU/EFTA 2010 173
6.8 Conclusion 183
Acknowledgements 185
References 185
7 Treating Missing Network Data Before Partitioning 189
Anja nidarÅ¡iÄ, Patrick Doreian, and AnuÅ¡ka Ferligoj
7.1 Introduction 189
7.2 Types of Missing Network Data 190
7.2.1 Measurement Errors in Recorded (Or Reported) Ties 190
7.2.2 Item Non-Response 192
7.2.3 Actor Non-Response 192
7.3 Treatments of Missing Data (Due to Actor Non-Response) 193
7.3.1 Reconstruction 194
7.3.2 Imputations of the Mean Values of Incoming Ties 196
7.3.3 Imputations of the Modal Values of Incoming Ties 196
7.3.4 Reconstruction and Imputations Based on Modal Values of Incoming Ties 197
7.3.5 Imputations of the Total Mean 197
7.3.6 Imputations of Median of the Three Nearest Neighbors based on Incoming Ties 197
7.3.7 Null Tie Imputations 198
7.3.8 Blockmodel Results for the Whole and Treated Networks 198
7.4 A Study Design Examining the Impact of Non-Response Treatments on Clustering Results 200
7.4.1 Some Features of Indirect and Direct Blockmodeling 200
7.4.2 Design of the Simulation Study 201
7.4.3 The Real Networks Used in the Simulation Studies 201
7.5 Results 202
7.5.1 Indirect Blockmodeling of Real Valued Networks 202
7.5.2 Indirect Blockmodeling on Real Binary Networks 210
7.5.3 Direct Blockmodeling of Binary Real Networks 216
7.6 Conclusions 222
Acknowledgements 223
References 223
8 Partitioning Signed Networks 225
Vincent Traag, Patrick Doreian, and Andrej Mrvar
8.1 Notation 225
8.2 Structural Balance Theory 226
8.2.1 Weak Structural Balance 230
8.3 Partitioning 232
8.3.1 Strong Structural Balance 233
8.3.2 Weak Structural Balance 237
8.3.3 Blockmodeling 238
8.3.4 Community Detection 239
8.4 Empirical Analysis 242
8.5 Summary and Future Work 247
References 248
9 Partitioning Multimode Networks 251
Martin G Everett and Stephen P Borgatti
9.1 Introduction 251
9.2 Two-Mode Partitioning 252
9.3 Community Detection 253
9.4 Dual Projection 254
9.5 Signed Two-Mode Networks 257
9.6 Spectral Methods 258
9.7 Clustering 261
9.8 More Complex Data 262
9.9 Conclusion 263
References 263
10 Blockmodeling Linked Networks 267
Aleš iberna
10.1 Introduction 267
10.2 Blockmodeling Linked Networks 268
10.2.1 Separate Analysis 269
10.2.2 A True Linked Blockmodeling Approach 269
10.2.3 Weighting of Different Parts of a Linked Network 270
10.3 Examples 270
10.3.1 Co-authorship Network at Two Time-points 270
10.3.2 A Multilevel Network of Participants at a Trade Fair for TV Programs 277
10.4 Conclusion 284
Acknowledgements 285
References 285
11 Bayesian Stochastic Blockmodeling 289
Tiago P. Peixoto
11.1 Introduction 289
11.2 Structure Versus Randomness in Networks 290
11.3 The Stochastic Blockmodel 292
11.4 Bayesian Inference: The Posterior Probability of Partitions 294
11.5 Microcanonical Models and the Minimum Description Length Principle 298
11.6 The âResolution Limitâ Underfitting Problem and the Nested SBM 300
11.7 Model Variations 305
11.7.1 Model Selection 306
11.7.2 Degree Correction 306
11.7.3 Group Overlaps 310
11.7.4 Further Model Extensions 313
11.8 Efficient Inference Using Markov Chain Monte Carlo 314
11.9 To Sample or To Optimize? 317
11.10 Generalization and Prediction 321
11.11 Fundamental Limits of Inference: The Detectabilityâ"Indetectability Phase Transition 323
11.12 Conclusion 327
References 328
12 Structured Networks and Coarse-Grained Descriptions: A Dynamical Perspective 333
Michael T. Schaub, Jean-Charles Delvenne, Renaud Lambiotte, and Mauricio Barahona
12.1 Introduction 333
12.2 Part I: Dynamics on and of Networks 337
12.2.1 General Setup 337
12.2.2 Consensus Dynamics 338
12.2.3 Diffusion Processes and Random Walks 340
12.3 Part II: The Influence of Graph Structure on Network Dynamics 342
12.3.1 Time Scale Separation in Partitioned Networks 342
12.3.2 Strictly Invariant Subspaces of the Network Dynamics and External Equitable Partitions 345
12.3.3 Structural Balance: Consensus on Signed Networks and Polarized Opinion Dynamics 348
12.4 Part III: Using Dynamical Processes to Reveal Network Structure 351
12.4.1 A Generic Algorithmic Framework for Dynamics-Based Network Partitioning and Coarse Graining 352
12.4.2 Extending the Framework by using other Measures 354
12.5 Discussion 357
Acknowledgements 358
References 358
13 Scientific Co-Authorship Networks 363
Marjan Cugmas, Anuška Ferligoj, and Luka Kronegger
13.1 Introduction 363
13.2 Methods 364
13.2.1 Blockmodeling 365
13.2.2 Measuring the Obtained Blockmodelsâ Stability 365
13.3 The Data 369
13.4 The Structure of Obtained Blockmodels 370
13.5 Stability of the Obtained Blockmodel Structures 378
13.5.1 Clustering of Scientific Disciplines According to Different Operationalizations of Core Stability 378
13.5.2 Explaining the Stability of Cores 382
13.6 Conclusions 384
Acknowledgements 386
References 386
14 Conclusions and Directions for Future Work 389
Patrick Doreian, Anuška Ferligoj, and Vladimir Batagelj
14.1 Issues Raised within Chapters 390
14.2 Linking Ideas Found in Different Chapters 395
14.3 A Brief Summary and Conclusion 397
References 397
Topic Index 399
Person Index 407
