Advances in Network Clustering and Blockmodeling E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Computational and Quantitative Social Science
• Sprache: Englisch

Seitenzahl: 830

Veröffentlichungsjahr: 2019

Beschreibung

Provides an overview of the developments and advances in the field of network clustering and blockmodeling over the last 10 years This book offers an integrated treatment of network clustering and blockmodeling, covering all of the newest approaches and methods that have been developed over the last decade. Presented in a comprehensive manner, it offers the foundations for understanding network structures and processes, and features a wide variety of new techniques addressing issues that occur during the partitioning of networks across multiple disciplines such as community detection, blockmodeling of valued networks, role assignment, and stochastic blockmodeling. Written by a team of international experts in the field, Advances in Network Clustering and Blockmodeling offers a plethora of diverse perspectives covering topics such as: bibliometric analyses of the network clustering literature; clustering approaches to networks; label propagation for clustering; and treating missing network data before partitioning. It also examines the partitioning of signed networks, multimode networks, and linked networks. A chapter on structured networks and coarsegrained descriptions is presented, along with another on scientific coauthorship networks. The book finishes with a section covering conclusions and directions for future work. In addition, the editors provide numerous tables, figures, case studies, examples, datasets, and more. * Offers a clear and insightful look at the state of the art in network clustering and blockmodeling * Provides an excellent mix of mathematical rigor and practical application in a comprehensive manner * Presents a suite of new methods, procedures, algorithms for partitioning networks, as well as new techniques for visualizing matrix arrays * Features numerous examples throughout, enabling readers to gain a better understanding of research methods and to conduct their own research effectively * Written by leading contributors in the field of spatial networks analysis Advances in Network Clustering and Blockmodeling is an ideal book for graduate and undergraduate students taking courses on network analysis or working with networks using real data. It will also benefit researchers and practitioners interested in network analysis.

Leseprobe

Table of Contents

Cover

List of Contributors

1 Introduction

1.1 On the Chapters

1.2 Looking Forward

2 Bibliometric Analyses of the Network Clustering Literature

2.1 Introduction

2.2 Data Collection and Cleaning

2.3 Analyses of the Citation Networks

2.4 Link Islands in the Clustering Network Literature

2.5 Authors

2.6 Summary and Future Work

Acknowledgements

References

Notes

3 Clustering Approaches to Networks

3.1 Introduction

3.2 Clustering

3.3 Approaches to Clustering

3.4 Clustering Graphs and Networks

3.5 Clustering in Graphs and Networks

3.6 Agglomerative Method for Relational Constraints

3.7 Some Examples

3.8 Conclusion

Acknowledgements

References

4 Different Approaches to Community Detection

4.1 Introduction

4.2 Minimizing Constraint Violations: the Cut-based Perspective

4.3 Maximizing Internal Density: the Clustering Perspective

4.4 Identifying Structural Equivalence: the Stochastic Block Model Perspective

4.5 Identifying Coarse-grained Descriptions: the Dynamical Perspective

4.6 Discussion

4.7 Conclusions

Acknowledgements

References

Note

5 Label Propagation for Clustering

5.1 Label Propagation Method

5.2 Label Propagation as Optimization

5.3 Advances of Label Propagation

5.4 Extensions to Other Networks

5.5 Alternative Types of Network Structures

5.6 Applications of Label Propagation

5.7 Summary and Outlook

References

Notes

6 Blockmodeling of Valued Networks

6.1 Introduction

6.2 Valued Data Types

6.3 Transformations

6.4 Indirect Clustering Approaches

6.5 Direct Approaches

6.6 On the Selection of Suitable Approaches

6.7 Examples

6.8 Conclusion

Acknowledgements

References

Notes

7 Treating Missing Network Data Before Partitioning

7.1 Introduction

7.2 Types of Missing Network Data

7.3 Treatments of Missing Data (Due to Actor Non-Response)

7.4 A Study Design Examining the Impact of Non-Response Treatments on Clustering Results

7.5 Results

7.6 Conclusions

Acknowledgements

References

Notes

8 Partitioning Signed Networks

8.1 Notation

8.2 Structural Balance Theory

8.3 Partitioning

8.4 Empirical Analysis

8.5 Summary and Future Work

References

Note

9 Partitioning Multimode Networks

9.1 Introduction

9.2 Two-Mode Partitioning

9.3 Community Detection

9.4 Dual Projection

9.5 Signed Two-Mode Networks

9.6 Spectral Methods

9.7 Clustering

9.8 More Complex Data

9.9 Conclusion

References

10 Blockmodeling Linked Networks

10.1 Introduction

10.2 Blockmodeling Linked Networks

10.3 Examples

10.4 Conclusion

Acknowledgements

References

Notes

11 Bayesian Stochastic Blockmodeling

11.1 Introduction

11.2 Structure Versus Randomness in Networks

11.3 The Stochastic Blockmodel

11.4 Bayesian Inference: The Posterior Probability of Partitions

11.5 Microcanonical Models and the Minimum Description Length Principle

11.6 The “Resolution Limit” Underfitting Problem and the Nested SBM

11.7 Model Variations

11.8 Efficient Inference Using Markov Chain Monte Carlo

11.9 To Sample or To Optimize?

11.10 Generalization and Prediction

11.11 Fundamental Limits of Inference: The Detectability–Indetectability Phase Transition

11.12 Conclusion

References

Notes

12 Structured Networks and Coarse-Grained Descriptions: A Dynamical Perspective

12.1 Introduction

12.2 Part I: Dynamics on and of Networks

12.3 Part II: The Influence of Graph Structure on Network Dynamics

12.4 Part III: Using Dynamical Processes to Reveal Network Structure

12.5 Discussion

Acknowledgements

References

13 Scientific Co-Authorship Networks

13.1 Introduction

13.2 Methods

13.3 The Data

13.4 The Structure of Obtained Blockmodels

13.5 Stability of the Obtained Blockmodel Structures

13.6 Conclusions

Acknowledgements

References

Notes

14 Conclusions and Directions for Future Work

14.1 Issues Raised within Chapters

14.2 Linking Ideas Found in Different Chapters

14.3 A Brief Summary and Conclusion

References

TOPIC INDEX

PERSON INDEX

End User License Agreement

List of Tables

Chapter 2

Table 2.1 Sizes of networks on clustering literature

Table 2.2 Sizes of “reduced” networks

Table 2.3 Sizes of networks with complete descriptions

Table 2.4 The most cited works in the network clustering literature

Table 2.5 The most citing works of the network clustering literature

Table 2.6 The most used journals in two works

journals networks

Table 2.7 The most used keywords

Table 2.8 List of works on CPM path (1), main paths (2), and island (3) – par...

Table 2.9 List of works on CPM path (1), main paths (2), and island (3) – par...

Table 2.10 List of works on CPM path (1), main paths (2), and island (3) – part ...

Table 2.11 List of works on CPM path (1), main paths (2), and island (3) – part ...

Table 2.12 List of works on CPM path (1), main paths (2), and island (3) – pa...

Table 2.13 Authors involved in the largest number of works

Table 2.14 Authors with the largest

-core values in

Table 2.15 Authors with the largest

-core values in

s

Table 2.16 Bibliographic coupling of the most cited works from the works of t...

Table 2.17 Bibliographic coupling in the three smaller islands

Table 2.18 The most frequent keywords of the two largest islands in the Jacca...

Chapter 3

Table 3.1 Dissimilarities on

Table 3.2 (Dis)similarities on

Table 3.3 The complexity of clustering problems

Table 3.4 Lance-Williams-Jambu coefficients

Table 3.5 Averages for Ward's clustering

Table 3.6 Averages for Maximum/Tolerant clustering

Table 3.7 The most cited authors/fractional approach

Chapter 5

Table 5.1 Degeneracy diagrams of the label propagation methods displaying the...

Table 5.2 Comparison of the label propagation methods on the signed Wikipedia...

Chapter 7

Table 7.1 Characteristics of the whole demonstration network and the seven tr...

Table 7.2 Cluster membership of the actors the whole demonstration network an...

Table 7.3 Characteristics of three real networks and binarized version of val...

Table 7.4 Summary of impact of actor non-response treatments on clustering

Chapter 10

Table 10.1 The weights used in a true linked approach

Table 10.2 Association of partition of the advice network and attribute varia...

Table 10.3 Association of partition of the contract network and attribute var...

Table 10.4 Association of the multilevel partition and the attribute variable...

Chapter 13

Table 13.1 Number of published scientific bibliographic units by type for two...

Table 13.2 The considered scientific disciplines and their characteristics in...

Table 13.3 The considered scientific disciplines and their characteristics in...

Table 13.4 The values of different indices for measuring the stability of cor...

Table 13.5 Basic descriptive statistics of the obtained clusters (averages on...

Table 13.6 The impact of the characteristics of the network, blockmodel, and ...

List of Illustrations

Chapter 2

Figure 2.1 Dyadic strong components.

Figure 2.2 The CPM path through the network clustering literature.

Figure 2.3 Key-route paths through the network clustering literature.

Figure 2.4 Valued networks main path with branches.

Figure 2.5 Signed network main path with branches.

Figure 2.6 Geophysics main path with branches.

Figure 2.7 Ten identified islands in the clustering network literature.

Figure 2.8 Island 10 community detection and blockmodeling.

Figure 2.9 Island 9 geophysics.

Figure 2.10

-cores at level 4 in

.

Figure 2.11 Links between authors in a

-core at level 3.5 in

.

Figure 2.12 Citations among authors from two parts of the literature: commun...

Figure 2.13

fractional islands.

Figure 2.14

main fractional island.

Figure 2.15 Bibliographic coupling.

Figure 2.16 Bibliographic coupling above a threshold set at 25.

Figure 2.17 Bibliographic coupling in the social networks literature.

Figure 2.18 Bibliographic coupling in the physicist-driven literature.

Figure 2.19 Bibliographic coupling – selected islands.

Figure 2.20 Bibliographic coupling for three smaller islands.

Figure 2.21 Authors Jaccard coupling – cut at level 11.

Figure 2.22 Journals Jaccard coupling – cut at level 1300.

Figure 2.23 Keywords Jaccard coupling – main island.

Chapter 3

Figure 3.1 Adding hierarchical method.

Figure 3.2 Neighbors exchange over an edge.

Figure 3.3 Examples of transformations.

Figure 3.4 Types of relational constraints.

Figure 3.5 A composite example.

Figure 3.6 The two-way strategy.

Figure 3.7 Ward clustering (left) and Maximum/Tolerant clustering (right).

Figure 3.8 Maximum/Tolerant partition on the map.

Figure 3.9 Subnetworks Wasserman and Ward.

Figure 3.10 Subnetworks Harary and Batagelj

Ferligoj.

Chapter 4

Figure 4.1 Schematic of four different approaches to community detection. (i...

Figure 4.2 Communities that highlight different aspects of networks. Identif...

Chapter 5

Figure 5.1 Label propagation in a small network with three communities. The ...

Figure 5.2 Resolution of ties between the maximal labels of the central node...

Figure 5.3 Label oscillations in bipartite and non-bipartite networks. The l...

Figure 5.4 The number of iterations of label propagation, the number of rela...

Figure 5.5 Comparison of defensive and offensive label propagation in artifi...

Figure 5.6 Performance of the label propagation methods in artificial networ...

Figure 5.7 Label propagation in artificial networks with planted community s...

Figure 5.8 Offensive label propagation with consensus clustering in the Euro...

Figure 5.9 Non-overlapping and overlapping label propagation in artificial n...

Figure 5.10 Artificial networks with two levels of planted community structu...

Figure 5.11 The meta-networks of the Google web graph and the Pennsylvania r...

Figure 5.12 Performance of the label propagation methods in artificial netwo...

Figure 5.13 Word clouds demonstrating two of the largest groups of nodes rev...

Chapter 6

Figure 6.1 Procedures for clustering valued data.

Figure 6.2 A “control chart” for choosing a suitable approach.

Figure 6.3 Binary generalized blockmodeling.

Figure 6.4 Valued generalized blockmodeling with

. The number above the mat...

Figure 6.5 Image matrices for valued generalized blockmodeling with

. The b...

Figure 6.6 Four-cluster partitions by selected approaches.

Figure 6.7 Results of sum of squares blockmodeling.

Figure 6.8 Valued gross degree (in- plus outdegree) of countries ordered by ...

Figure 6.9 The distribution of the original and log-transformed tie values....

Figure 6.10 Results of sum of squares blockmodeling on the log-transformed n...

Figure 6.11 Scree diagram for the absolute deviations approach on an iterate...

Figure 6.12 Six-cluster partition obtained using absolute deviations on an i...

Figure 6.13 Valued blockmodeling results with

using an iterated row-column...

Figure 6.14 Dendrogram plus four-cluster solution for hierarchical clusterin...

Figure 6.15 Dendrogram and the five-cluster solution for hierarchical cluste...

Figure 6.16 Dendrogram and four-cluster solution for Ward's hierarchical clu...

Chapter 7

Figure 7.1 A demonstration network with ten actors.

Figure 7.2 The matrix representation of the demonstration network with erron...

Figure 7.3 The matrix representation of the demonstration network with item ...

Figure 7.4 The matrix representation of the demonstration network with three...

Figure 7.5 Results of seven actor non-response treatments for the demonstrat...

Figure 7.6 The confirmed networks for seeking work-related information and p...

Figure 7.7 Matrix and graphical representations of the note-borrowing networ...

Figure 7.8 A valued network from a police academy with a partition obtained ...

Figure 7.9 Dendrograms for the indirect blockmodeling of the confirmed (valu...

Figure 7.10 The two valued networks with partitions obtained from indirect b...

Figure 7.11 Results of the simulation study for the indirect blockmodeling o...

Figure 7.12 Dendrogram of the

network.

Figure 7.13 Results of the simulation study for the indirect blockmodeling o...

Figure 7.14 Dendrogram and results of the simulation study for the indirect ...

Figure 7.15 Dendrograms for the indirect blockmodeling of the binarized conf...

Figure 7.16 Binarized networks with partitions from indirect blockmodeling....

Figure 7.17 Results of the simulation study for the indirect blockmodeling o...

Figure 7.18 Results of the simulation study for the direct blockmodeling of ...

Figure 7.19 Networks with partitions from direct blockmodeling based on stru...

Figure 7.20 Results of the simulation study for the direct blockmodeling of ...

Figure 7.21 Results for the direct blockmodeling of the binarized confirmed ...

Chapter 8

Figure 8.1 Structural balance. There are four possible configurations for ha...

Figure 8.2 Chords and cycles. This illustrates a cycle

with a chord betwee...

Figure 8.3 Switching. On the left, there are three edges crossing the partit...

Figure 8.4 Balance timeline. The line index of imbalance using two different...

Figure 8.5 International relations 1944. The solid lines represent positive ...

Figure 8.6 International relations 1939. The solid lines represent positive ...

Figure 8.7 A map of the weak balance partition in 1962.

Figure 8.8 Map of CPM partition with

in 2010.

Chapter 9

Figure 9.1 Group assignment maximizing modularity.

Figure 9.2 Dual projection core-periphery of Southern Women.

Figure 9.3 Dual projection community detection for the Davis data.

Figure 9.4 Dual projection community detection for four groups.

Figure 9.5 Spectral bisection of the Davis data into two groups.

Figure 9.6 Spectral bisection of the Davis data into four groups.

Chapter 10

Figure 10.1 The linked network representation of the co-authorship network i...

Figure 10.2 Blockmodeling of the first period (1991–2000) only.

Figure 10.3 Blockmodeling of the second period (2001–2010) only.

Figure 10.4 Linked view of the separately obtained partitions.

Figure 10.5 Results of linked blockmodeling with five clusters in each perio...

Figure 10.6 Results of linked blockmodeling with five clusters in each perio...

Figure 10.7 Results of linked blockmodeling with four clusters in each perio...

Figure 10.8 Original (unpartitioned) multilevel network of advice (persons

Figure 10.9 Blockmodeling of the advice relation among persons.

Figure 10.10 Results of blockmodeling of the contract network among organiza...

Figure 10.11 Results of the separate analysis presented on a multilevel netw...

Figure 10.12 Results of a true multilevel/linked approach with five clusters...

Figure 10.13 Results of a true multilevel/linked approach with four clusters...

Chapter 11

Figure 11.1 The three panels show the same adjacency matrix, with the only d...

Figure 11.2 SBM: (a) the matrix of probabilities between groups

defines th...

Figure 11.3 Bayesian inference of the SBM for a network of American college ...

Figure 11.4 Inference of the SBM on a simple artificial network composed of ...

Figure 11.5 (a) Diagrammatic representation of the nested SBM described in t...

Figure 11.6 Fit of the (degree-corrected) nested SBM for the internet topolo...

Figure 11.7 Inferred partition for a network of political blogs [2] using (a...

Figure 11.8 Illustration of the generative process of the microcanonical DC-...

Figure 11.9 Most likely hierarchical partitions of a network of political bl...

Figure 11.10 Network of co-purchases of books about US politics [54], with g...

Figure 11.11 (a) Artificial network sampled from an assortative overlapping ...

Figure 11.12 Efficient MCMC strategies. (a) Move proposals are made by inspe...

Figure 11.13 Posterior distribution of partitions of Zachary's karate club n...

Figure 11.14 Hierarchical partitions of a network of collaboration between s...

Figure 11.15 Two hypothetical missing edges in the network of American colle...

Figure 11.16 Normalized mutual information (NMI) between the planted and inf...

Chapter 12

Figure 12.1 Consensus dynamics on the Karate Club network. (a) The Karate Cl...

Figure 12.2 Illustration of the evolution of a random walk dynamics on the K...

Figure 12.3 Consensus dynamics on a structured network. (a) Visualization of...

Figure 12.4 The external equitable partition and its dynamical implications....

Figure 12.5 Example of a structurally balanced graph. A structurally balance...

Figure 12.6 Polarized opinion dynamics in structurally balanced networks. (a...

Figure 12.7 Schematic of the algorithmic framework for partitioning of netwo...

Chapter 13

Figure 13.1 The features that can be used as indicators of less stable clust...

Figure 13.2 Indices for measuring the stability of cores in time (the featur...

Figure 13.3 A list of scientific disciplines with the number of researchers ...

Figure 13.4 Structure of the sociology co-authorship blockmodel for the firs...

Figure 13.5 Visualization of researchers' transitions in two time periods fo...

Figure 13.6 Visualization of researchers' transitions between the cores in t...

Figure 13.7 The average core size and the average size of the periphery by f...

Figure 13.8 Distribution of standardized values of the first canonical discr...

Figure 13.9 Visualizations of researchers' transitions between the cores, in...

Guide

Cover

Table of Contents

Begin Reading

Pages

ii

iii

iv

v

xv

xvi

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

Wiley Series in Computational and Quantitative Social Science

Computational Social Science is an interdisciplinary field undergoing rapid growth due to the availability of ever increasing computational power leading to new areas of research.

Embracing a spectrum from theoretical foundations to real world applications, the Wiley Series in Computational and Quantitative Social Science is a series of titles ranging from high level student texts, explanation and dissemination of technology and good practice, through to interesting and important research that is immediately relevant to social / scientific development or practice. Books within the series will be of interest to senior undergraduate and graduate students, researchers and practitioners within statistics and social science.

Behavioral Computational Social Science

Riccardo Boero

Tipping Points: Modelling Social Problems and Health

John Bissell (Editor), Camila Caiado (Editor), Sarah Curtis (Editor), Michael Goldstein (Editor), Brian Straughan (Editor)

Understanding Large Temporal Networks and Spatial Networks: Exploration, Pattern Searching, Visualization and Network Evolution

Vladimir Batagelj, Patrick Doreian, Anuška Ferligoj, Nataša Kejžar

Analytical Sociology: Actions and Networks

Gianluca Manzo (Editor)

Computational Approaches to Studying the Co-evolution of Networks and Behavior in Social Dilemmas

Rense Corten

The Visualisation of Spatial Social Structure

Danny Dorling

ADVANCES IN NETWORK CLUSTERING AND BLOCKMODELING

Edited by

Patrick Doreian

University of Pittsburgh, USAUniversity of Ljubljana, Slovenia

Vladimir Batagelj

University of Ljubljana and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia University of Primorska, Andrej Marušič Institute, Koper, Slovenia NRU High School of Economics, Moscow, Russia

Anuška Ferligoj

University of Ljubljana, Slovenia NRU High School of Economics, Moscow, Russia

This edition first published 2020© 2020 John Wiley & Sons Ltd

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Patrick Doreian, Vladimir Batagelj, and Anuška Ferligoj to be identified as the authors of the editorial material in this work has been asserted in accordance with law.

Registered OfficesJohn Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USAJohn Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

Editorial Office9600 Garsington Road, Oxford, OX4 2DQ, UK

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print-on-demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of WarrantyWhile the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging-in-Publication Data

Names: Doreian, Patrick, editor. | Batagelj, Vladimir, 1948- editor. | Ferligoj, Anuška, editor.

Title: Advances in network clustering and blockmodeling / Patrick Doreian, Vladimir Batagelj, Anuška Ferligoj.

Description: Hoboken, NJ : Wiley, 2020. | Series: Wiley series in computational and quantitative social science | Includes bibliographical references and index.

Identifiers: LCCN 2019024475 (print) | LCCN 2019024476 (ebook) | ISBN 9781119224709 (cloth) | ISBN 9781119224686 (adobe pdf) | ISBN 9781119224679 (epub)

Subjects: LCSH: Social networks–Mathematical models. | Sociometry.

Classification: LCC HM741 .A35 2020 (print) | LCC HM741 (ebook) | DDC 302.301/13–dc23

LC record available at https://lccn.loc.gov/2019024475

LC ebook record available at https://lccn.loc.gov/2019024476

Cover Design: WileyCover Image: Courtesy of Vladimir Batagelj

We dedicate this book to the memories of Sue Freeman and Lin Freeman because of their impacts on our lives in both professional and personal realms. Together, they formed a fine couple living a rich and full life. Together, they provided a kind of role model worthy of emulation.

Lin founded and was a longtime editor of Social networks. For decades it was the premier journal of the field. While joined by other network venues, it remains the primary home for scholars publishing papers about social networks. He had a clear vision for the role this journal could play as a venue for publishing important work and how it could help to define our field. Especially important was the breath of his commitment to encouraging interdisciplinary work across multiple fields. He was very catholic in encouraging multiple approaches and different ways of doing research. But he was clear that this work had to be rigorous and done within sound research designs.

Both Lin and Sue were social active at the annual Sunbelt Social Network conferences both in sessions and, more importantly, outside sessions when a lot of ideas are generated in free-flowing discussions about our field and potential future directions.

Editors

List of Contributors

Mauricio BarahonaDepartment of Mathematics, Imperial College London, London, UK; EPSRC Centre for Mathematics of Precision Healthcare, Imperial College London, London, UK

Vladimir BatageljProfessor Emeritus, Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia; University of Primorska, Andrej Marušič Institute, Koper, Slovenia; NRU High School of Economics, Moscow, Russia

Steve BorgattiLINKS Center for Social Network Analysis, Gatton College of Business and Economics, University of Kentucky, Lexington, KY, USA

Marjan CugmasFaculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia

Jean-Charles DelvenneICTEAM and CORE, Université Catholique de Louvain, Belgium

Patrick DoreianProfessor Emeritus, Department of Sociology, University of Pittsburgh, Pittsburgh, USA; Faculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia

Martin EverettSchool of Social Sciences, University of Manchester, Manchester, United Kingdom

Anuška FerligojFaculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia; NRU High School of Economics, Moscow, Russia

Luka KroneggerFaculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia

Renaud LambiotteMathematical Institute, University of Oxford; Entités de recherche: Institut Namurois des systèmes complexes (naXys), University of Namur, Namur, Belgium

Andrej MrvarFaculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia

Carl NordlundThe Institute for Analytical Sociology, Linköping University, Sweden; Center for Network Science, Central European University, Hungary

Tiago P. PeixotoDepartment of Mathematical Sciences and Centre for Networks and Collective Behaviour, University of Bath, United Kingdom; ISI Foundation, Turin, Italy

Martin RosvallDepartment of Physics, Umeå University, Umeå, Sweden

Michael SchaubInstitute for Data, Systems and Society, Massachusetts Institute of Technology; Department of Engineering Sciences, University of Oxford

Lovro ŠubeljFaculty of Computer and Information Science, University of Ljubljana, Ljubljana, Slovenia

Vincent TraagCentre for Science and Technology Studies, Leiden University, Leiden, The Netherlands

Aleš ŽibernaFaculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia

Anja ŽnidaršičFaculty of Organizational Sciences, University of Maribor, Maribor, Slovenia

1Introduction

Patrick Doreian3,4, Vladimir Batagelj1,2,5 and Anuška Ferligoj3,5

1IMFM Ljubljana

2IAM, University of Primorska, Koper

3FDV, University of Ljubljana

4University of Pittsburgh

5NRU HSE Moscow

This book focuses on network clustering regardless of the disciplines within which a network was established. In the initial conception for the book, our attention was driven primarily by concerns regarding blockmodeling and community detection as they applied to social networks. But as we looked further into this general topic to invite potential contributors, we realized that the domain was much broader. The wide variety of approaches contained in this volume exemplifies this diversity. For us, as we assembled this volume, this was an exciting learning experience, one we hope will be experienced by readers of this book.

There is no single best approach to network clustering. Put differently, there is no cookie-cutter approach fitting all such data sets. Yes, there are adherents of one (their) approach who think this is the case. As shown in the chapters that follow, none of the authors of the contributed chapters share this very narrow view. This is a wide-open realm with multiple exciting approaches. We reflect further on this in the concluding chapter. Here, we describe briefly the contents of the following chapters merely as an introduction to them. In our view, each chapter merits close attention.

1.1 On the Chapters

As the book is concerned with network clustering, Chapter 2 offers an extended examination of the network clustering literature. Identifying the citation network for this literature turned out to be a complex task. Methods for doing this are described in detail. The initial search used the Web of Science (WoS) to identify documents using search terms. There were multiple searches, with the first being for 2015 and the final network was obtained for February 2017. This literature expanded dramatically and in a complex fashion.

While a citation network is composed of links between works treated as nodes, there is more to consider when other types of units are included. These include authors, journals, and keywords. As part of a more general strategy, one starting from the citation network but using additional information, multiple two-mode networks were constructed. This included an authorship network with works authors, a journal network featuring works journals, and a keyword network with works keywords. They help give more insight into the one-mode citation network having only scientific productions.

Chapter 2 lists the most cited works, the most citing works, the most used keywords, and a discussion of the “boundary problem” as it relates to citation networks. One message from this chapter is that the way the boundary of a citation network is established affects greatly the data analytic results that follow. This implies using great care in constructing citation networks – not all citation networks will suffice for meaningful analyses.

Chapter 2 presents a wide range of analyses of the citation network for the network clustering literature. Components of the network were established. Both critical project main paths and key-route paths were identified. In the analysis of this network, a clear transition between the blockmodeling and the community detection literatures was revealed. Another technique used in Chapter 2 is the identification of link islands which have higher levels of internal cohesion as a way identifying some important subnetworks of this literature. The largest of these link islands featured works from the blockmodeling and community detection literatures. Since the transition from the former to the latter, it seems the two have developed independently. This seems problematic given our belief in the utility of useful ideas flowing between fields and sub-fields.

The other islands discussed in Chapter 2 come from the fields of engineering geology, geophysics, as well as electromagnetic fields and their impacts on humans. One of the searches used in the searches of the WoS database included the terms “block model” and “block”. The latter crops up in other literatures, a surprise for us. In considering these other link islands, another surprise awaited the authors of this chapter. We are used to debates in the social network literature regarding the difference between static and temporal approaches to studying networks. This divide is present also in the natural sciences.

Chapter 2 also contains an examination of authors and measures of productivity within research groups, collaboration, and an examination of citations among authors contributing to the network clustering literature. Again, the stark division between the community detection and blockmodeling literatures was clear. Examined also are citations between journals publishing articles in the broad area of the network clustering literature. The methodological details of doing this, as outlined in this chapter, merit further attention.

Bibliographic coupling, which occurs when two works both cite a third work in their bibliographies, was also examined. This included a sustained assessment as to how this coupling is measured. These tools were applied to the network clustering literature, especially for the largest identified island. This included an examination of the most frequently used keywords in the social networks literature and the physicist-driven approach to studying social networks. While some keywords were the same, there were considerable differences, again illustrating the different concerns in these two literatures.

Chapter 3 provides an overview of “classical” clustering including both the clustering of networks and clustering in networks. The clustering problem is considered as a discrete optimization problem which turns to be, in most cases, NP hard. Therefore, local optimization or greedy methods are usually used for solving it. These methods can be adapted also for clustering in networks (or clustering with relational constraints). The hierarchical agglomerative clustering method can be extended for efficiently clustering large sparse networks. This is illustrated with an analysis of normalized author citation networks from the network clustering literature from Chapter 2.

Chapter 4 describes different approaches to community detection. The authors ask very useful questions which led them to provide helpful guidelines for researchers contemplating network clustering within a community detection framework. It starts with a bold claim that there is no precise definition of a community. We concur. Their focused review of community detection methods makes it clear that researchers need to have a clear idea as to why any method is selected prior to its use. The authors point to the problem that the same term can have different meanings in different subfields, reflecting what was found in Chapter 2. They argue “community detection should not be viewed as a well-defined problem but rather an umbrella term with many facets.” This delightful image is equally applicable to blockmodeling within social network analysis!

Four different approaches to community detection are outlined. The first uses the cut-based perspective. The second is a clustering approach maximizing the internal density of clusters and the third is the stochastic equivalence perspective. Finally, there is a dynamical perspective focusing on the impact of communities and dynamic processes to establish a dynamically relevant coarse-grained partitions of network structure. Four sections follow which provide precise descriptions of the fundamental properties of these approaches and the results stemming from adopting them.

Their discussion makes it clear that there is no single “best” community detection algorithm and that there can be multiple equally valid partitions of a network depending on which of the four considered approaches is used. Again, this sentence holds fully when “blockmodeling” is used instead of “community detection”. Of course, this applies to all the network clustering approaches presented in this volume.

Chapter 5 provides an extensive discussion of label propagation as a heuristic method initially proposed for community detection. There is natural segue between Chapters 4 and 5. Label propagation is a partially supervised machine learning algorithm assigning labels to previously unlabeled data points. At the start of the algorithm, subsets of nodes have labels, which amounts to a clustering of them. These labels are propagated to the unlabeled points throughout the course of the algorithm. Nodes carry a label denoting the community to which they belong. Membership in a community changes based on the labels that the neighboring nodes possess as the labels diffuse through the network.

The author is clear that while it is not the most accurate or the most robust clustering method, a label propagation algorithm is simple to implement and is exceptionally fast. Networks with hundreds of millions of nodes can be analyzed readily. The early work on this approach is described with the basic ideas presented for simple undirected networks. However, the author points out that it can be used for many more types of networks, including those with multiple edges between nodes, two-mode networks, and signed networks. It can be used also to identify and delineate overlapping clusters: it is not restricted to establishing only partitions of nodes, a useful property. Nested hierarchies of groups of nodes can be identified also.

Issues regarding the number of clusters are discussed along with updating labels, which can be done with either synchronous propagation or asynchronous propagation. Depending on the structure of the network, each can produce undesirable outcomes, which are discussed in detail. Reaching an equilibrium with nodes having stable labels is critical and ways for achieving this are discussed.

Advances in label propagation methods are described. They include adding constraints to the objective function to prevent trivial solutions, using preferences to adjust the propagation strength of nodes, and improving algorithmic performance by promoting its stability and reducing its complexity. Simple examples with planted communities are provided and used to show the subtlety of the method and the choices made when using it. A connection is made with the blockmodeling literature when using structural equivalence, consistent with the general conception motivating the book to apply and connect different methods for establishing clusters of network nodes.

Chapter 6 marks a transition from community detection issues to blockmodeling concerns. There is now an abundant amount of valued network data being collected and made available. As the initial work on blockmodeling dealt with binary networks, extending and adapting this approach to handle valued networks is important. The authors show that creating this extension is far from straightforward because subtle issues arise as to how valued network data can be treated prior to blockmodeling them. The authors discuss the difference between the traditional indirect approach and the direct approach to blockmodeling. In the former, networks are transformed into arrays expressing the similarity, or dissimilarity, of the nodes. These measures are then used to cluster the nodes. Their Figure 6.1 lays out the relevant decision points. In contrast, the direct approach eschews such transformations. Within the rubric of generalized blockmodeling, network data are analyzed directly. For valued networks, the authors cleave to the latter approach by making strategic adaptations to handle valued data in useful ways. This includes homogeneity blockmodeling championed by one of the authors and deviation generalized blockmodeling promoted by the other contributing author.

Two well-known empirical data sets were selected for a detailed examination of the issues involved in blockmodeling valued data. The simplest of the two is a friendship network. The second involves trade flows between nations, one raising the issue of relational capacity. This has major implications for the nature of discerning the relevant useful transformations. As with the previous chapters in this volume, close attention is paid to the choices that must be made regarding the appropriateness of methods given the data being analyzed and the criteria for making these choices. Their Figure 6.2 is particularly important as a way of guiding researchers to make appropriate decisions. It could be generalized more broadly and adapted for the other network clustering approaches presented in this volume.

By presenting detailed analyses of the selected empirical networks using different approaches and a variety of transformations, the authors show, and examine, the different outcomes resulting from making different strategic choices. The results have interest value in their own right, and lead to a set of useful recommendations about these choices. Some open problems are discussed briefly.

Chapter 7 continues the consideration of blockmodeling but tackles a very different issue, namely, measurement error. The premise for blockmodeling is that using these methods reveals the structural features of networks at both the macro and micro levels. The presence of measurement error complicates these analyses. In the worst case scenario it can render blockmodeling results useless. Three types of measurement errors are discussed. One takes the form of having errors in the recorded ties. The second is item non-response and the third is actor non-response.

Actor non-response is the primary focus of this chapter. Typically, and regrettably, within social network analysis, the standard response to this problem is to discard all information about the non-respondents, including information about the ties directed to them by respondents. This discarded information can be used to recover (most of) the network. The authors contend that this must be done and provide strong evidence supporting this claim. The question that follows is simple to state: how is this done?

The authors present seven ways for using such data as imputation methods for recovering the network from the ravages of actor non-response: reconstruction, imputation using the mean of the incoming ties, imputation with modal values of the incoming ties, reconstruction combined with using the incoming modal values, imputation of the total mean, imputations using the median of the three nearest neighbors based on incoming ties, and null tie imputation.

The authors examine the relative merits of these ways of recovering network data using four known empirical networks. Five steps are involved. The first establishes a partition of the known network within the indirect blockmodeling approach. The second step creates “observed” networks by randomly removing some actors (at various levels ranging from 1% to over 45%). Step three involves using each of the imputation methods to generate recovered networks. The fourth step is the clustering of each recovered network using the exact same clustering method as in the first step. The final step compares the partitions for all pairs of known and recovered networks. Two criteria were used in the comparisons. One is the Adjusted Rand Index for comparing two partitions. The other is the proportion of correctly identified blocks by position in the blockmodel. These criteria are stringent and there are clear differences regarding the adequacy of imputation methods. As with the foregoing chapters, recommendations are made regarding the best ways for recovering network data given the presence of actor non-response.

Chapter 8 addresses the clustering of signed networks, a topic that has garnered considerable attention within both the blockmodeling and community detection literatures. The authors adopt a formal approach and start within the structural balance perspective, which is a substantively driven approach to studying signed networks. The basics of this approach are reviewed. Some of the early theorems are restated with some new proofs provided. One critical feature of structural balance theory states that a signed network is balanced if all its cycles are balanced. But cycles can vary in length, a feature that complicates algorithms used for determining the extent to which graphs are imbalanced. The authors use the concept of chords, which allows cycles to have two subcycles which simplifies computing the sign of a cycle.

One prominent feature of the balance theoretic approach centers on what has come to be called the “structure theorems”. Initially, if a signed graph was balanced, its nodes could be partitioned into two clusters such that all the positive ties were in one cluster and all the negative ties went between the two clusters. Later, this was extended to any number of clusters having this property. Here, the authors call the former strong structural balance and the latter weak structural balance. One interesting theorem in this chapter states that signed graphs are weakly structurally balanced if and only if all chordless cycles are weakly structurally balanced.

The authors then turn to consider the clustering of signed networks in a more general fashion. For strong structural balance, they couple this approach to spectral theory. They rework an early concept of switching (from a 1958 paper) to prove theorems relating to balance in signed networks using this concept. For weak structural balance, one allowing for more than two clusters, additional ideas have emerged. The structure theorems point to a blockmodel where diagonal blocks are positive (with primarily positive ties) and non-diagonal blocks are negative (with primarily negative ties). Yet empirical networks can come in the form of having off-diagonal positive blocks and, far more rarely, on-diagonal negative blocks. As the authors note, more research is required regarding the distribution of signed blocks in a blockmodel. They consider also community detection issues for signed networks and note that one of the main concepts of this approach, modularity, has problems when there are negative links in the network. They provide ways of addressing this problem.

The authors address the critical problem of studying temporal networks in a dynamic context and, as an empirical example, study the international system with signed relation between nations. They display timeline graphs showing variations in the levels of imbalance in the international system using different methods. They confirm that signed networks move both towards balance and away from balance depending on contexts. Their results add to the solid argument against the early presumption of structural balance theorists that signed networks always move towards balance. Also displayed are partitions of nations for various time points, which are interpreted in interesting ways.

Chapter 9 presents a summary of work on multimode network clustering and illustrates the results of using different methods on a single well-known early two-mode network. One of the conceptions behind this volume is bringing together ideas from multiple disciplines. Actually, the authors of this chapter engage in this process explicitly. While they focus on two-mode networks in the form of actors events as a bipartite network, the implications of the materials in this chapter extend much further. Although such two-mode networks have been considered in earlier chapters, especially Chapter 2, having an integrated discussion of the ways in which they can be analyzed is particularly useful. They note that both binary and valued two-mode networks can be analyzed within a common rubric. Multiple such methods are discussed in the chapter.

The authors establish a conceptual link to community detection, make some definitions to help link the two literatures, and note that community detection is a special case of blockmodeling. The same point was made in Chapter 4. Some authors focused on community detection methods might disagree! Here, the core community detection notion of modularity is provided and, more importantly, the authors extend this to two-mode networks. Their first presented partition (of actors) concerns group assignment maximizing modularity.

Given a two-mode network, denoted , it is straightforward to create two projections for actors, using , and events, using . They challenge the presumption that evidence is lost in this dual projection. Without doubt, as the authors note, this holds when projections are dichotomized or if only one projection is used. However, they challenge the claim that dual projection loses information even when both projections are used in their undichotomized forms. Elsewhere, they have provided strong evidence that this is not the case and have promoted what they call the dual-projection approach. They present further partitions of the actors of the considered empirical network using dual-projection, using core-periphery notions and for dual-projection community detection. The latter led to two more partitions, one with two clusters and one with four clusters of actors.

In their spirit of integration, the authors include a consideration of signed two-mode networks and a consideration of spectral methods. Two more partitions of the actors are presented. As with previous chapters, it seems reasonable to have multiple valid partitions of a network. The authors finish with suggestions regarding the analyses of more complex data structure involving more modes and extend this to temporal evolution of two-mode networks.

Chapter 10 is devoted to blockmodeling linked networks and provides another segue in this volume. This time it is from Chapter 9. The term “linked networks” features a set of one-mode networks where the nodes from the one-mode networks are linked through two-mode networks. This can be done in a variety of ways, including the coupling of networks linked over multiple time points. In dealing with these configurations, the author distinguishes analyses of separate networks, using a conversion approach under which all the one-mode networks are converted to a single level by joining them through the two-mode networks, and using a genuine multilevel approach. The results of examining both the conversion to a single level and using the multilevel approach are presented. Comparisons of them demonstrate clearly how the linked blockmodeling approach has greater potential value.

Two empirical examples are used. One concerns a coauthorship network at two time points while the other features participants in a fair-trade exchange for TV programs. In both examples, results of different partitions are presented with insightful comparisons of the results. As with all methods, parameter settings require consideration. For these analyses, this concerns the weighting of null and complete blocks for the scientific citation network. The final reported results provide a very coherent result with strikingly clear differences in the partitions for two distinct time points, which provide useful interpretations of the dynamics of scientific collaboration. The empirical results resulting from using the genuine multilevel method for the trade fair are equally compelling. As with other chapters, the author provides a provisional agenda for future work.

Chapter 11 provides a self-contained introduction to using Bayesian inference to extract the large-scale modular structure from network data. In terms of the foregoing content of this chapter, the modules are clusters (or groups) identified in the network. Rather than focus on deterministic blockmodeling, Chapter 11 deals with Bayesian stochastic blockmodeling. A major focus is on estimating probabilistic models to shed light on the network mechanisms generating the observed network(s). An overarching feature is to distinguish genuine structure from randomness.

In this context, Figure 11.1 is especially provocative, with three displays of a randomly generated network having three separate orderings of the nodes. Two of them appear to show clear – but different – blockmodel structures, exactly the sort that those using deterministic blockmodeling would take as evidence of structure. While these blockmodels could be accepted as “real” and could be “interpreted”, this would reveal nothing about the generative process creating the network. This might rattle the cages of some social network blockmodelers. The author invites readers to think probabilistically and couple two ideas. One is to think about mechanisms that could generate networks. The other is to use the network data to discern which mechanism was the most likely to have generated the network. This leads directly to notion of stochastic blockmodels within which known (prescribed) modular structures are generated according to probabilistic rules. Then, given network data, Bayesian inference is used to infer the modular structure of observed networks.

The author provides formal discussions of a wide variety of prior distributions and how data affect them to create posterior distributions. Many empirical applications are used to illustrate the outcomes stemming from using the methods described in formal detail. This includes the subtleties of model selection and the establishment of efficient estimation procedures. The ultimate outcome is the establishment of modular structures that are supported by statistical evidence.

Chapter 12 also focuses on a dynamical perspective. Both this chapter and Chapter 11 are concerned with modular structures having a coarse grain, along with the rich interplay between network structures and network dynamics. However, the authors of Chapter 12 take a very different approach compared with the one contained in Chapter 11. Their concern is centered on the dynamical processes occurring on a fixed network structure. They do not consider, at least initially, the question of how and why networks occur. Throughout their presentation, they focus on consensus dynamics and diffusion processes both substantively and as guiding examples. Later, they consider diffusion and consensus as dual processes, an important extension.

For modeling dynamics, they use ordinary differential equations in which the actors have attributes that can be changed by the operation of social processes operating over a fixed network. While discrete-time versions could be used, they use continuous-time models throughout their chapter. Also, of great interest, they consider processes having different network time scales under which some variables change slowly while others change more quickly. They illustrate this with a modular network having modules with strong within coupling and weak between coupling. More complicated structures are examined also.

The authors extend this approach to consider signed networks and use the early work on structural balance theory while restricting their attention to strong balance as described in Chapter 8. The early structural balance literature was fixated on the notion that signed networks always move towards balance. This claim is repeated here. A far more important issue is the examination of how (and why) signed networks move towards balance at some points in time and move way from balance at other times. It would seem that the author's use of using differential equations, as is done in Chapter 12, for signed networks holds immense promise for examining these dynamics, especially with the inclusion of different time scales.

Later in their chapter, the authors turn to using dynamical processes to reveal network structure within the community detection framework. They employ a genetic algorithm framework to do this with a variety of extensions, all of which hold considerable promise. As with previous chapters, some open problems are stated with interesting methodological and substantive implications if they are pursued in a dynamic framework using differential equations.

Chapter 13 is the final contributed chapter, one that examines scientific coauthorship networks. A blockmodeling approach is adopted to understand the structure of these networks with a view to understanding the dynamics of scientific knowledge production. The data used feature collaboration among Slovene scientists using a rich temporal database. While blockmodeling can be used to discern the structure of these networks at multiple points in time, one particularly interesting question is whether these blockmodels, especially the composition of positions (clusters) and the relationships between positions (blocks) are stable over time. The authors of this chapter present a methodology for measuring the stability of such blockmodels over time. Of particular interest is the stability (or not) of cores. For this important task, a variety of indices are proposed for assessing this stability.

Science is dynamic in many ways. Of particular interest in Chapter 13 is the changing relationships between researchers through time. Over the course of their careers, the collaborative behavior of researchers changes as new problems engage their interests and collaborative partners change. Also, some researchers depart while new researchers enter the scientific system. The authors of this chapter consider first one discipline that has a core-periphery structure (with cores, a semi-periphery, and a periphery) at the two time periods they consider. They developed a visualization for transitions between these positions. This is then extended to consider 43 disciplines. For each identified discipline, they identify changes in the number of cores, the average size of them, and the relative sizes of the semi-periphery and the periphery.

The authors use a variety of different indices for measuring the stability of cores for all the studied scientific disciplines. They establish a partition of disciplines into three clusters. The smallest cluster has eight disciplines for which the cores are stable. The next smallest is a cluster of 13 disciplines whose cores are unstable. The largest cluster has 22 disciplines that are located between these extremes. One implication is that science in not monolithic. While is it obvious that disciplines have different concerns in terms of content, these results reveal clearly how their collaboration structures vary greatly. The authors present results showing why this is the case.

1.2 Looking Forward

Even though the single focus of network clustering defines the impulse behind this volume, the topic has many facets within which many approaches have been adopted. In looking at the contributed chapters, there is great diversity in the topics considered and the approaches taken by the contributing authors. This was expected and was core to constructing this volume. There are many points of consistency across the chapters along with apparent disagreements. The former is great. The latter is not a problem for there will always be diverse views in this literature. We compliment all the contributing authors for their willingness to contribute in an open-minded and engaged fashion. While many academic disciplines have been riven by deep divides across which no compromise is possible, our hope is that the consideration of the network clustering literature presented in this volume will allow us to rise above such foolish divides. The contributed chapters suggest this is very possible.

So, to our readers of this volume, we hope you will enjoy the contributions in each of the contributed chapters. Each has great merit. We will return to some of the general issues raised within each of the chapters, as well joining issues from these chapters, in the concluding chapter.

2Bibliometric Analyses of the Network Clustering Literature

Vladimir Batagelj1,2,5, Anuška Ferligoj3,5 and Patrick Doreian3,4

1IMFM Ljubljana

2IAM, University of Primorska, Koper

3FDV, University of Ljubljana

4University of Pittsburgh

5NRU HSE Moscow

2.1 Introduction

Partitioning networks is performed in many disciplines, as is evidenced by the chapters of this book. The data we consider here are from the network clustering literature. Our focus here is the large set of publications identified in the area of graph/network clustering and blockmodeling, and included in the Web of Science1 (WoS) through February 2017. The two dominant approaches for clustering networks are found in the “social” social network literature and the literature featuring physicists and other scientists examining networks. Blockmodeling is an approach that partitions the nodes of a network into positions (clusters of nodes) with the blocks being the sets of relationships within and between positions. The result is a simplified image of the whole network. Community detection, associated with the work of physicists studying networks, aims to identify communities composed of nodes having a higher probability of being connected to each other than to members of other communities