Advances in Network Clustering and Blockmodeling

1 Introduction to the book 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 15 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 Keyroute paths 20 2.3.4 Positioning sets of selected works in a citation network 30 2.4 Link islands in the clustering network literature 34 2.4.1 Island 10: Community Detection and Blockmodeling 35 2.4.2 Island 7: Engineering Geology 37 2.4.3 Island 9: Geophysics 37 2.4.4 Island 2: Electromagnetic fields and their impact on humans 38 2.4.5 Limitations and extensions 39 2.5 Authors 40 2.5.1 Productivity inside research groups 41 2.5.2 Collaboration 41 2.5.3 Citations among authors contributing the network partitioning literature 44 2.5.4 Citations among journals 46 2.5.5 Bibliographic Coupling 49 2.5.6 Linking through a Jaccard network 56 2.6 Summary and future work 58 References 60 3 Clustering approaches to networks 63 Vladimir Batagelj 3.1 Introduction 63 3.2 Clustering 64 3.2.1 The clustering problem 64 3.2.2 Criterion functions 65 3.2.3 Clustererror function / examples 69 3.2.4 The complexity of the clustering problem 72 3.3 Approaches to Clustering 73 3.3.1 Local optimization 73 3.3.2 Dynamic programming 75 3.3.3 Hierarchical methods 76 3.3.4 Adding hierarchical methods 79 3.3.5 The leaders method 80 3.4 Clustering Graphs and Networks 82 3.5 Clustering in Graphs and Networks 84 3.5.1 An indirect approach 84 3.5.2 A direct approach - blockmodeling 85 3.5.3 Graph theoretic approaches 85 3.6 Agglomerative method for relational constraints 86 3.6.1 Software support 90 3.7 Some examples 90 3.7.1 The US geographical data, 2016 90 3.7.2 Citations among authors from the network clustering literature 94 3.8 Conclusion 98 References 99 4 Different approaches to community detection 103 Martin Rosvall, JeanCharles Delvenne, Michael T. Schaub, and Renaud Lambiotte 4.1 Introduction 103 4.2 Minimizing constraint violations: the cutbased perspective 105 4.3 Maximizing internal density: the clustering perspective 106 4.4 Identifying structural equivalence: the stochastic block model perspective 108 4.5 Identifying coarsegrained descriptions: the dynamical perspective 109 4.6 Discussion 112 4.7 Conclusions 114 4.8 Acknowledgements 114 References 114 5 Label Propagation for Clustering 119 Lovro Subelj 5.1 Label Propagation Method 119 5.1.1 Resolution of Label Ties 121 5.1.2 Order of Label Propagation 121 5.1.3 Label Equilibrium Criterium 122 5.1.4 Algorithm and Complexity 123 5.2 Label Propagation as Optimization 124 5.3 Advances of Label Propagation 125 5.3.1 Label Propagation under Constraints 126 5.3.2 Label Propagation with Preferences 128 5.3.3 Method Stability and Complexity 130 5.4 Extensions to Other Networks 133 5.5 Alternative Types of Network Structures 134 5.5.1 Overlapping Groups of Nodes 135 5.5.2 Hierarchy of Groups of Nodes 136 5.5.3 Structural Equivalence Groups 137 5.6 Applications of Label Propagation 140 5.7 Summary and Outlook 141 References 142 6 Blockmodeling of valued networks 147 Carl Nordlund and Ales iberna 6.1 Introduction 147 6.2 Valued data types 149 6.3 Transformations 150 6.3.1 Scaling transformations 151 6.3.2 Dichotomization 152 6.3.3 Normalization procedures 152 6.3.4 Iterative row column normalization 153 6.3.5 Transactionflow and deviational transformations 154 6.4 Indirect clustering approaches 155 6.4.1 Structural equivalence: indirect metrics 155 6.4.2 The CONCOR algorithm 156 6.4.3 Deviational structural equivalence: indirect approach 157 6.4.4 Regular equivalence: the REGE algorithms 157 6.4.5 Indirect approaches: finding clusters, interpreting blocks 158 6.5 Direct approaches 159 6.5.1 Generalized blockmodeling 159 6.5.2 Generalized blockmodeling of valued networks 160 6.5.3 Deviational generalized blockmodeling 161 6.6 On the selection of suitable approaches 161 6.7 Examples 162 6.7.1 EIES friendship data at time 2 164 6.7.2 Commodity trade within EU/EFTA 2010 169 6.8 Conclusion 178 References 181 7 Treating missing network data before partitioning 185 Anja nidar si?, Patrick Doreian, and Anuska Ferligoj 7.1 Introduction 185 7.2 Types of missing network data 186 7.2.1 Measurement errors in recorded (or reported) ties 186 7.2.2 Item nonresponse 188 7.2.3 Actor nonresponse 189 7.3 Treatments of missing data (due to actor nonresponse) 189 7.3.1 Reconstruction 190 7.3.2 Imputations of the mean values of incoming ties 191 7.3.3 Imputations of the modal values of incoming ties 192 7.3.4 Reconstruction and imputations based on modal values of incoming ties 193 7.3.5 Imputations of the total mean 193 7.3.6 Imputations of median of the 3nearest neighbours based on incoming ties 193 7.3.7 Null tie imputations 194 7.3.8 Blockmodel results for the whole and treated networks 194 7.4 A study design examining the impact of nonresponse treatments on clustering results 196 7.4.1 Some features of indirect and direct blockmodeling 196 7.4.2 Design of the simulation study 196 7.4.3 The real networks used in the simulation studies 197 7.5 Results 200 7.5.1 Indirect blockmodeling of real valued networks 200 7.5.2 Indirect blockmodeling on real binary networks 203 7.5.3 Direct blockmodeling of binary real networks 208 7.6 Conclusions 211 References 214 8 Partitioning signed networks 217 Vincent Traag, Patrick Doreian, and Andrej Mrvar 8.1 Notation 217 8.2 Structural balance theory 218 8.2.1 Weak structural balance 222 8.3 Partitioning 224 8.3.1 Strong structural balance 224 8.3.2 Weak structural balance 229 8.3.3 Blockmodelling 229 8.3.4 Community detection 230 8.4 Empirical analysis 233 8.5 Summary and Future Work 237 References 239 9 Partitioning Multimode Networks 243 Martin G Everett, and Stephen P Borgatti 9.1 Introduction 243 9.2 2 Mode partitioning 244 9.3 Community Detection 245 9.4 Dual Projection 247 9.5 Signed 2mode networks 250 9.6 Spectral methods 251 9.7 Clustering 253 9.8 More complex data 254 9.9 Conclusion 255 References 255 10 Partitioning linked networks 259 Ales iberna 10.1 Introduction 259 10.2 Blockmodeling linked networks 260 10.2.1 Separate analysis 261 10.2.2 A true linked blockmodeling approach 261 10.2.3 Weighting of different parts of a linked network 262 10.3 Examples 262 10.3.1 Coauthorship network at two timepoints 262 10.3.2 A multilevel network of participants at a trade fair for TV programs 269 10.4 Conclusion 277 References 278 11 Bayesian stochastic blockmodeling 281 Tiago P. Peixoto 11.1 Introduction 281 11.2 Structure versus randomness in networks 282 11.3 The stochastic blockmodel (SBM) 283 11.4 Bayesian inference: the posterior probability of partitions 286 11.5 Microcanonical models and the minimum description length principle (MDL) 290 11.6 The "resolution limit" underfitting problem, and the nested SBM 292 11.7 Model variations 297 11.7.1 Model selection 297 11.7.2 Degree correction 298 11.7.3 Group overlaps 302 11.7.4 Further model extensions 304 11.8 Efficient inference using Markov chain Monte Carlo (MCMC) 305 11.9 To sample or to optimize? 308 11.10 Generalization and prediction 312 11.11 Fundamental limits of inference: the detectability indetectability phase transition 314 11.12 Conclusion 318 References 318 12 Structured networks and coarsegrained descriptions: a dynamical perspective 325 Michael T. Schaub, JeanCharles Delvenne, Renaud Lambiotte, and Mauricio Barahona 12.1 Introduction 325 12.2 Part I - Dynamics on and of networks 328 12.2.1 General setup 328 12.2.2 Consensus dynamics 329 12.2.3 Diffusion processes and random walks 331 12.3 Part II - The influence of graph structure on network dynamics 333 12.3.1 Time scale separation in partitioned networks 333 12.3.2 Strictly invariant subspaces of the network dynamics and external equitable partitions 336 12.3.3 Structural balance: consensus on signed networks and polarised opinion dynamics 339 12.4 Part III - Using dynamical processes to reveal network structure 342 12.4.1 A generic algorithmic framework for dynamics based network partitioning and coarse graining 342 12.4.2 Extending the framework by using other measures 344 12.5 Discussion 347 References 348 13 Scientific coauthorship networks 355 Marjan Cugmas, Anuska Ferligoj, and Luka Kronegger 13.1 Introduction 355 13.2 Methods 357 13.2.1 Blockmodeling 357 13.2.2 Measuring the obtained blockmodels' stability 357 13.3 The data 359 13.4 The structure of obtained blockmodels 361 13.5 Stability of the obtained blockmodel structures 369 13.5.1 Clustering of scientific disciplines according to different operationalizations of core stability 371 13.5.2 Explaining the stability of cores 373 13.6 Conclusions 375 References 377 14 Conclusions and directions for future work 381 Patrick Doreian, Anuska Ferligoj, and Vladimir Batagelj 14.1 Issues raised within chapters 382 14.2 Linking ideas found in different chapters 387 14.3 A brief summary and conclusion 389 References 389

Este título pertence ao(s) assunto(s) indicados(s). Para ver outros títulos clique no assunto desejado.

• Electrónica e engenharia das comunicações