Presented in a comprehensive manner, this book provides a comprehensive foundation in algebraic approaches for the analysis of different types of social networks such as multiple, signed, and affiliation networks. The study of such configurations corresponds to the structural analysis within the social sciences, and the methods applied for the analysis are in the areas of abstract algebra, combinatorics, and graph theory.
Current research in social networks has moved toward the examination of more realistic but also more complex social relations by which agents or actors are connected in multiple ways. Addressing this trend, this book offers hands-on training of the algebraic procedures presented along with the computer package multiplex, written by the book’s author specifically to perform analyses of multiple social networks. An introductory section on both complex networks and for R will feature, however the subjects themselves correspond to advanced courses on social network analysis with the specialization on algebraic models and methods.
Table of Contents
List of Figures xvii
List of Tables xxi
Preface xxiii
Abbreviations xxv
Symbols xxvii
About the Companion Website xxxi
1 Structural Analysis with Algebra 1
1.1 Preliminaries 1
1.2 Graphs 2
1.2.1 Graphs and Digraphs 2
1.2.2 Multigraphs 3
1.2.3 Signed Graph 3
1.2.4 Bipartite Graph 4
1.2.5 Valued Graph 4
1.2.6 Multilevel Graph 5
1.3 Matrices 5
1.3.1 Affiliation Matrix 5
1.3.2 Multiple Relations 6
1.3.3 Incidence Matrix 6
1.3.4 Valency Matrix 6
1.3.5 Different Systems 7
1.3.6 Graph and Matrix Representations 7
1.4 Chains, Paths, and Other Graph Properties 8
1.5 Algebra of Relations 9
1.5.1 Generators and Compounds 9
1.6 Operations on Social Networks 10
1.6.1 Binary Operation on Relations 10
1.6.2 Relational Composition 11
1.7 Types and Properties of Relations 13
1.8 Equivalence and Ordering 14
1.8.1 Equivalence 14
1.8.2 Partial Order 15
1.8.3 Hierarchy 16
1.9 Functions 16
1.9.1 Identity and Empty Functions 18
1.9.2 Transformations 19
1.10 Homomorphism and Congruence 19
1.10.1 Congruence Relations 20
1.10.2 Kernel of a Homomorphism 20
1.11 Structural Analysis with Algebra: Summary 21
1.12 Learning Structural Analysis by Doing 22
1.12.1 Getting Started 22
1.12.2 Matrices 22
1.12.3 Graphs 23
2 Algebraic Structures 25
2.1 Algebraic Structure Definition 25
2.1.1 Closure 25
2.2 Group Structure 26
2.2.1 Cayley Graph 27
2.2.2 Permutation Groups 28
2.2.3 Presentation of Group Structures 29
2.3 Group of Symmetries: Dihedral Groups 30
2.3.1 Group of Symmetries of the Equilateral Triangle 30
2.3.2 Group of Symmetries of the Square 32
2.3.3 Generating Set in Symmetric Groups 34
2.4 Semigroup 34
2.4.1 Semigroup of Relations 35
2.5 Semigroup and Group Properties 36
2.5.1 Regular Elements 36
2.5.2 Subsemigroups and Ideals 36
2.6 Ring and Semiring 37
2.6.1 Semiring 37
2.7 Lattice Structure 38
2.7.1 Congruence Lattice 39
2.7.2 Modular and Distributive Lattice 40
2.8 Algebraic Structures: Summary 41
2.9 Learning Algebraic Structures by Doing 42
2.9.1 Dihedral Group of the Equilateral Triangle D3 42
2.9.2 Dihedral Group of the Square D4 44
2.9.3 Modular and Nonmodular Lattices 46
3 Multiplex Network Configurations 49
3.1 Multiple Networks 49
3.1.1 Types of Multiple Networks 50
3.2 Kinship Networks and Group Structure 51
3.2.1 Marriage Types in Kinship Systems 52
3.3 Rules for Marriage and Descent in the Kariera Society 53
3.3.1 Group Structure and Set of Equations 55
3.4 Algebraic Constraints 56
3.5 Link Generalizations and Complex Structures 57
3.6 Bundle Patterns 58
3.6.1 Bundle Class Properties 59
3.6.2 Bundle Isomorphic Classes 60
3.6.3 Statistical Approach to Bundle Patterns 61
3.7 Co-occurrence of Ties Model 62
3.8 Relational Structure 64
3.8.1 Strength of Weak Ties Model as Relational Structure 65
3.8.2 Graph Representation of the Strength of Weak Ties 66
3.9 Semigroup of Relations in Multiplex Networks 68
3.9.1 Partial Order Relations and the Axiom of Quality 69
3.9.2 Multiplication Table 71
3.10 Partially Ordered Semigroup 74
3.10.1 Partial Ordering in XZ 75
3.11 Word and Edge Tables 76
3.12 Multiplex Network Configurations: Summary 77
3.13 Learning Multiplex Networks by Doing 78
3.13.1 Kariera Kinship Network 78
3.13.2 Multiplex Networks 79
3.13.3 Strength of Weak Ties 80
3.13.4 Relational Structure 80
4 Positional Analysis and Role Structure 83
4.1 Roles and Positions 83
4.2 Network Homomorphism 84
4.2.1 Weak and Strong Graph Homomorphisms 85
4.2.2 Juncture Graph Homomorphism 86
4.3 Global Equivalences 87
4.3.1 Structural Equivalence 88
4.3.2 Automorphic Equivalence 88
4.3.3 Regular Equivalence 89
4.3.4 Generalized Equivalence 90
4.4 Global Equivalences Applied 91
4.5 Local Equivalences 94
4.5.1 Relation-Box R(W) 94
4.5.2 Relation Plane and Role Relations in R(W) 95
4.5.3 Local Role Equivalence 96
4.6 Compositional Equivalence 97
4.6.1 Formal Definition of Compositional Equivalence 98
4.7 Positional Analysis with Compositional Equivalence 99
4.7.1 Cumulated Person Hierarchy, H 99
4.7.2 Set of Generators in Complex Networks 101
4.7.3 Incorporating Actor Attributes 102
4.8 Positional Analysis and Role Structure: Summary 104
4.9 Learning Positional Analysis and Role Structure by Doing 105
4.9.1 Equivalence Relations 105
5 Role Structure in Multiplex Networks 109
5.1 Directed Role Structures: Incubator Network A 110
5.1.1 Social Positions in Network XA 111
5.1.2 Modeling XA with Compositional Equivalence 112
5.1.3 Cumulated Person Hierarchy HA 114
5.1.4 Positional System SA 116
5.2 Role Structure Incubator Network A 119
5.2.1 Constructing Role Structures 120
5.2.2 Particular Elements in the Role Structure 121
5.2.3 Role Structure with Relational Contrast 122
5.3 Undirected Role Structures: Florentine Families Network 125
5.3.1 Positional Analysis of the Florentine Families Network 125
5.3.2 Constructing Person Hierarchies, HF 127
5.3.3 Family Attributes in XF 129
5.4 Role Structure of the Florentine Families Network 132
5.4.1 Interlock of Business, Marriage and Wealth Role Relations in QF 134
5.4.2 Inclusion of Role Relations 135
5.5 Role Structure in Multiplex Networks: Summary 137
5.6 Learning Role Structure in Multiplex Networks by Doing 138
5.6.1 Incubator Network A 138
5.6.2 Florentine Families Network, XF 139
5.6.3 Role Structure of XF with Wealth 141
6 Decomposition of Role Structures 145
6.1 Aggregation and Decomposition 145
6.1.1 Homomorphic Reductions 147
6.2 Synthesis Rules 147
6.2.1 Direct Representation 147
6.2.2 Subdirect Representation 148
6.3 Lattice of Congruence Relations 149
6.4 Factorization 150
6.4.1 Atoms and their Meet-Complements 150
6.4.2 Lattice of Homomorphisms of the Semigroup 151
6.5 Congruences by Substitution Property 152
6.6 Aggregation of Role Structures in QA 153
6.6.1 Atoms with Meet-Complements in Role Structure QA 154
6.6.2 Congruence Lattice L𝜋(QA) 156
6.7 Role Interlock of Incubator Network A 159
6.7.1 Factorizing Set 159
6.7.2 Hierarchy of Relations in QA 164
6.8 Progressive Homomorphic Reduction of Factors in QA 166
6.9 Role Structure for Incubator Network B 169
6.9.1 Factorization of QB 169
6.9.2 Congruence by Substitution Property in QB 170
6.10 Role Interlock of Incubator Network C 172
6.10.1 Decomposition of QC 172
6.11 Role Interlock of QF for Florentine Families Network 173
6.11.1 Congruence Classes in Role Structure QF 174
6.12 Reduction Diagram 177
6.13 Decomposition of Role Structures: Summary 179
6.14 Learning Decomposition of Role Structures by Doing 180
6.14.1 Factorization of Role Structure QA 180
6.14.2 Decomposition of Florentine Families Role Structure QF 183
6.14.3 Decomposition of Role Structure QB 185
7 Signed Networks 187
7.1 Structural Analysis of Signed Networks 187
7.2 Social Influence Process 188
7.2.1 Cohesion Influence 188
7.2.2 Comparison and Influence 190
7.3 Structural Balance 191
7.3.1 Balance and Relational Composition 193
7.4 Semirings for Structural Balance 195
7.4.1 Valence Rules for Balance Semirings 196
7.4.2 Closure Operations in Semirings 199
7.5 Balance and Comparison Influence 199
7.5.1 Weak Balanced Structures 201
7.6 Looking for Structural Balance 201
7.6.1 Balance Semiring in Signed Network X 𝜎 A 203
7.6.2 Cluster Semiring in Signed Network X 𝜎 A 208
7.7 Signed Networks: Summary 209
7.8 Learning Signed Networks by Doing 210
7.8.1 Signed Structures in Figure 7.1 210
7.8.2 Balance Semiring Structures in a Signed Triad 210
7.8.3 Structural Balance in Incubator Network A, XA 211
7.8.4 Balance Structures in Table 7.4 211
8 Affiliation Networks 215
8.1 Structural Analysis of Affiliation Networks 215
8.1.1 Visualization and Partition of Two-mode Data 216
8.1.2 Binomial Projection 218
8.2 Common Affiliations 220
8.2.1 Actors Perspective 220
8.2.2 Events Perspective 222
8.2.3 Affiliation Network with Bridge Organizations X B G20b 223
8.3 Formal Concept Analysis 224
8.4 Formal Concepts and Galois Derivations 225
8.4.1 Concepts in the G20 Affiliation Network 226
8.5 Concept Lattice and Ordering of Concepts 228
8.5.1 Partial Ordering of the Concepts 228
8.5.2 Concept Lattice of the Context 228
8.5.3 Concept Lattice of Network X B G20 230
8.6 Order Filters and Order Ideals 232
8.6.1 Principal Order Filters 232
8.6.2 Order Ideals and Principal Order Ideals 233
8.7 Affiliation Networks: Summary 234
8.8 Learning Affiliation Networks by Doing 235
8.8.1 G20 Affiliation Network 235
8.8.2 Bipartite Graphs in X B G20 235
8.8.3 Co-affiliation Network of G20 Network 236
8.8.4 Positional System of X B G20b with Events Classes 236
8.8.5 Clustered Bipartite Graph and Binomial Projection of X B G20b 238
8.8.6 Formal Concept Analysis 238
8.8.7 Order Filters and Order Ideals 240
9 Valued Networks 241
9.1 Relational Structure of Valued Networks 242
9.1.1 Valued Paths in the G20 Trade Network 242
9.1.2 Constructing Valued Paths 245
9.1.3 Semigroup and Equations of Valued Relations 246
9.1.4 First Letter Law in Semigroup Structure 247
9.2 Many-valued Contexts 249
9.2.1 Conceptual Scaling 249
9.2.2 Conceptual Scaling of X B G20 250
9.2.3 Concept Lattices Concept lattices of Many-valued Contexts 253
9.3 Pathfinder Network Analysis 255
9.3.1 Pathfinder Semiring Pathfinder semiring 256
9.3.2 Pathfinder Algorithm 257
9.4 Pathfinder Semiring to Co-affiliation Network in X B G20 258
9.5 Triangle Inequality 259
9.5.1 Application of Triangle Inequality triangle inequality to a Valued Configuration 260
9.5.2 Triangle Inequality triangle inequality in Multiplex Networks 261
9.6 Trade Network X V G20 with Triangle Inequality 262
9.7 Valued Networks: Summary 264
9.8 Learning Valued Networks by Doing 265
9.8.1 Valued Network 265
9.8.2 Semigroup of Valued Network with max-min Product 266
9.8.3 Many-valued Contexts 267
9.8.4 Pathfinder Semiring 269
9.8.5 Triangle Inequality 271
10 Multilevel Networks 273
10.1 Structural Analysis of Multilevel Systems 273
10.2 Visual Representation of Clients and Attorneys Multilevel Network 274
10.2.1 Additional Features 276
10.3 Multilevel Structure of the G20 Network 276
10.3.1 Multilevel structure of all G20 countries X M G20 276
10.4 Multilevel Positional System of G20 Network with Bridges 279
10.4.1 Visual Interpretation of the Multilevel Structure in X B G20b 280
10.4.2 Positional Analysis of X M G20b 282
10.4.3 Depiction of Multilevel Positional System SM G20b 283
10.5 Algebraic Approaches to Multilevel Networks 284
10.5.1 G20 Multilevel Network 285
10.5.2 Visualization of Multilevel Network Algebra 287
10.5.3 Substantial Interpretation 289
10.6 Reducing Complexity in X M G20b 289
10.7 Further Algebraic Representations of Multilevel Structures 291
10.8 Multilevel Networks: Summary 292
10.9 Learning Multilevel Networks by Doing 293
10.9.1 Multilevel Network ‘Clients and Attorneys’ 293
10.9.2 Multilevel Structure of G20 Network with Bridges 294
10.9.3 Multilevel Structure of G20 Trade and Affiliation Networks 295
10.9.4 Positional System for the Algebraic Analysis 296
10.9.5 Relational Structure of Multilevel Configurations 297
10.9.6 Two-class Multilevel Positional System 299
11 Comparing Relational Structures 301
11.1 Comparing Structures with Algebraic Constraints 302
11.2 Incubator Networks B and C 303
11.2.1 Positional Analysis of XB and XC 303
11.3 Equality 307
11.3.1 Set of Equations in Incubator Role Structures 307
11.4 Hierarchy of Relations 310
11.4.1 Set of Inclusions in Incubator Networks 311
11.5 Shared Structure by Role Tables 312
11.5.1 Lattice of Homomorphisms of the Semigroup 312
11.5.2 Joint Homomorphic Reduction, JNTHOM 314
11.5.3 Common Structure Semigroup, CSS 314
11.5.4 What Constitutes a “Shared” Structure? 315
11.6 Semigroup Tables with Joint Homomorphic Reduction 316
11.6.1 JNTHOM of Aggregated Role tables QA 316
11.6.2 JNTHOM of Aggregated Role tables QB and QC 317
11.6.3 Joint Table for Incubator Networks 318
11.7 Comparison Across Networks with Common Structure Semigroup 319
11.7.1 CSS for Incubator networks A, B, and C 321
11.7.2 CSS Order Role Structure for QA-B-C 324
11.8 Comparing Structures in Substantial Terms 324
11.8.1 Hierarchy of Social Relations and Actor Attributes 324
11.8.2 Set of Equations or Equality in QA, QB, and QC 327
11.9 Structuring Effect of Role Relations in Incubators 327
11.10 Comparing Relational Structures: Summary 329
11.11 Learning Comparing Relational Structures by Doing 330
11.11.1 Visualization of Incubator Networks B and C 330
11.11.2 Positional Analysis and Role Structure for XB and XC 330
11.11.3 Decomposition of QB and QC 331
11.11.4 Equalities in Incubator Networks 333
A Datasets 335
Kariera kinship 335
Incubators A, B, C 335
Florentine families 336
Clients and attorneys 336
Group of twenty 336
B Role structures of Incubator networks 339
Role Structure of XA 339
Role Structure of XB 339
Positional system of Incubator network B 339
Role tables in QB 341
Role Structure of XC 342
Positional system of Incubator network C 342
C Valued data in G20 Trade network 347
Group of Twenty Indicators 347
Commodities in G20 Trade valued network 348
Units of measure of G20 country data 348
G20 Trade valued network and salient structures 348
D Layout visualization algorithms 353
Force-directed 353
Stress-majorization 355
Laplacian Function 358
New stress internal function 359
E Role structure workflow 361
Decomposition of Role structure QB 361
Incubator network B 361
Positional analysis and Role structure 361
Factorization 362
Progressive factorization of Factors 363
Aggregated structure of QB 370
Bibliography 371
Index 377
