List of Contributors xv 1 Introduction 1 Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj 1.1 On the Chapters 1 1.2 Looking Forward 9 2 Bibliometric Analyses of the Network Clustering Literature 11 Vladimir Batagelj, Anuska 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 Subelj 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 Ales Ziberna 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 Znidarsi?, Patrick Doreian, and Anuska 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 Ales Ziberna 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 Gener.