J. ANTONIO RIVERO OSTOIC, PHD, is a post doctorate fellow at the School of Culture and Society, Aarhus University, Denmark, and a research associate at the University of San Simón (CESU). With a background in sociology and social sciences his research is mainly focused on social networks. He developed the R packages multiplex and multigraph for performing algebraic analysis and visualization of complex systems.

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...