Algebraic Analysis of Social Networks

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 xviiList of Tables xxiPreface xxiiiAbbreviations xxvSymbols xxviiAbout the Companion Website xxxi1 Structural Analysis with Algebra 11.1 Preliminaries 11.2 Graphs 21.2.1 Graphs and Digraphs 21.2.2 Multigraphs 31.2.3 Signed Graph 31.2.4 Bipartite Graph 41.2.5 Valued Graph 41.2.6 Multilevel Graph 51.3 Matrices 51.3.1 Affiliation Matrix 51.3.2 Multiple Relations 61.3.3 Incidence Matrix 61.3.4 Valency Matrix 61.3.5 Different Systems 71.3.6 Graph and Matrix Representations 71.4 Chains, Paths, and Other Graph Properties 81.5 Algebra of Relations 91.5.1 Generators and Compounds 91.6 Operations on Social Networks 101.6.1 Binary Operation on Relations 101.6.2 Relational Composition 111.7 Types and Properties of Relations 131.8 Equivalence and Ordering 141.8.1 Equivalence 141.8.2 Partial Order 151.8.3 Hierarchy 161.9 Functions 161.9.1 Identity and Empty Functions 181.9.2 Transformations 191.10 Homomorphism and Congruence 191.10.1 Congruence Relations 201.10.2 Kernel of a Homomorphism 201.11 Structural Analysis with Algebra: Summary 211.12 Learning Structural Analysis by Doing 221.12.1 Getting Started 221.12.2 Matrices 221.12.3 Graphs 232 Algebraic Structures 252.1 Algebraic Structure Definition 252.1.1 Closure 252.2 Group Structure 262.2.1 Cayley Graph 272.2.2 Permutation Groups 282.2.3 Presentation of Group Structures 292.3 Group of Symmetries: Dihedral Groups 302.3.1 Group of Symmetries of the Equilateral Triangle 302.3.2 Group of Symmetries of the Square 322.3.3 Generating Set in Symmetric Groups 342.4 Semigroup 342.4.1 Semigroup of Relations 352.5 Semigroup and Group Properties 362.5.1 Regular Elements 362.5.2 Subsemigroups and Ideals 362.6 Ring and Semiring 372.6.1 Semiring 372.7 Lattice Structure 382.7.1 Congruence Lattice 392.7.2 Modular and Distributive Lattice 402.8 Algebraic Structures: Summary 412.9 Learning Algebraic Structures by Doing 422.9.1 Dihedral Group of the Equilateral Triangle D3 422.9.2 Dihedral Group of the Square D4 442.9.3 Modular and Nonmodular Lattices 463 Multiplex Network Configurations 493.1 Multiple Networks 493.1.1 Types of Multiple Networks 503.2 Kinship Networks and Group Structure 513.2.1 Marriage Types in Kinship Systems 523.3 Rules for Marriage and Descent in the Kariera Society 533.3.1 Group Structure and Set of Equations 553.4 Algebraic Constraints 563.5 Link Generalizations and Complex Structures 573.6 Bundle Patterns 583.6.1 Bundle Class Properties 593.6.2 Bundle Isomorphic Classes 603.6.3 Statistical Approach to Bundle Patterns 613.7 Co-occurrence of Ties Model 623.8 Relational Structure 643.8.1 Strength of Weak Ties Model as Relational Structure 653.8.2 Graph Representation of the Strength of Weak Ties 663.9 Semigroup of Relations in Multiplex Networks 683.9.1 Partial Order Relations and the Axiom of Quality 693.9.2 Multiplication Table 713.10 Partially Ordered Semigroup 743.10.1 Partial Ordering in XZ 753.11 Word and Edge Tables 763.12 Multiplex Network Configurations: Summary 773.13 Learning Multiplex Networks by Doing 783.13.1 Kariera Kinship Network 783.13.2 Multiplex Networks 793.13.3 Strength of Weak Ties 803.13.4 Relational Structure 804 Positional Analysis and Role Structure 834.1 Roles and Positions 834.2 Network Homomorphism 844.2.1 Weak and Strong Graph Homomorphisms 854.2.2 Juncture Graph Homomorphism 864.3 Global Equivalences 874.3.1 Structural Equivalence 884.3.2 Automorphic Equivalence 884.3.3 Regular Equivalence 894.3.4 Generalized Equivalence 904.4 Global Equivalences Applied 914.5 Local Equivalences 944.5.1 Relation-Box R(W) 944.5.2 Relation Plane and Role Relations in R(W) 954.5.3 Local Role Equivalence 964.6 Compositional Equivalence 974.6.1 Formal Definition of Compositional Equivalence 984.7 Positional Analysis with Compositional Equivalence 994.7.1 Cumulated Person Hierarchy, H 994.7.2 Set of Generators in Complex Networks 1014.7.3 Incorporating Actor Attributes 1024.8 Positional Analysis and Role Structure: Summary 1044.9 Learning Positional Analysis and Role Structure by Doing 1054.9.1 Equivalence Relations 1055 Role Structure in Multiplex Networks 1095.1 Directed Role Structures: Incubator Network A 1105.1.1 Social Positions in Network XA 1115.1.2 Modeling XA with Compositional Equivalence 1125.1.3 Cumulated Person Hierarchy HA 1145.1.4 Positional System SA 1165.2 Role Structure Incubator Network A 1195.2.1 Constructing Role Structures 1205.2.2 Particular Elements in the Role Structure 1215.2.3 Role Structure with Relational Contrast 1225.3 Undirected Role Structures: Florentine Families Network 1255.3.1 Positional Analysis of the Florentine Families Network 1255.3.2 Constructing Person Hierarchies, HF 1275.3.3 Family Attributes in XF 1295.4 Role Structure of the Florentine Families Network 1325.4.1 Interlock of Business, Marriage and Wealth Role Relations in QF 1345.4.2 Inclusion of Role Relations 1355.5 Role Structure in Multiplex Networks: Summary 1375.6 Learning Role Structure in Multiplex Networks by Doing 1385.6.1 Incubator Network A 1385.6.2 Florentine Families Network, XF 1395.6.3 Role Structure of XF with Wealth 1416 Decomposition of Role Structures 1456.1 Aggregation and Decomposition 1456.1.1 Homomorphic Reductions 1476.2 Synthesis Rules 1476.2.1 Direct Representation 1476.2.2 Subdirect Representation 1486.3 Lattice of Congruence Relations 1496.4 Factorization 1506.4.1 Atoms and their Meet-Complements 1506.4.2 Lattice of Homomorphisms of the Semigroup 1516.5 Congruences by Substitution Property 1526.6 Aggregation of Role Structures in QA 1536.6.1 Atoms with Meet-Complements in Role Structure QA 1546.6.2 Congruence Lattice L𝜋(QA) 1566.7 Role Interlock of Incubator Network A 1596.7.1 Factorizing Set 1596.7.2 Hierarchy of Relations in QA 1646.8 Progressive Homomorphic Reduction of Factors in QA 1666.9 Role Structure for Incubator Network B 1696.9.1 Factorization of QB 1696.9.2 Congruence by Substitution Property in QB 1706.10 Role Interlock of Incubator Network C 1726.10.1 Decomposition of QC 1726.11 Role Interlock of QF for Florentine Families Network 1736.11.1 Congruence Classes in Role Structure QF 1746.12 Reduction Diagram 1776.13 Decomposition of Role Structures: Summary 1796.14 Learning Decomposition of Role Structures by Doing 1806.14.1 Factorization of Role Structure QA 1806.14.2 Decomposition of Florentine Families Role Structure QF 1836.14.3 Decomposition of Role Structure QB 1857 Signed Networks 1877.1 Structural Analysis of Signed Networks 1877.2 Social Influence Process 1887.2.1 Cohesion Influence 1887.2.2 Comparison and Influence 1907.3 Structural Balance 1917.3.1 Balance and Relational Composition 1937.4 Semirings for Structural Balance 1957.4.1 Valence Rules for Balance Semirings 1967.4.2 Closure Operations in Semirings 1997.5 Balance and Comparison Influence 1997.5.1 Weak Balanced Structures 2017.6 Looking for Structural Balance 2017.6.1 Balance Semiring in Signed Network X 𝜎 A 2037.6.2 Cluster Semiring in Signed Network X 𝜎 A 2087.7 Signed Networks: Summary 2097.8 Learning Signed Networks by Doing 2107.8.1 Signed Structures in Figure 7.1 2107.8.2 Balance Semiring Structures in a Signed Triad 2107.8.3 Structural Balance in Incubator Network A, XA 2117.8.4 Balance Structures in Table 7.4 2118 Affiliation Networks 2158.1 Structural Analysis of Affiliation Networks 2158.1.1 Visualization and Partition of Two-mode Data 2168.1.2 Binomial Projection 2188.2 Common Affiliations 2208.2.1 Actors Perspective 2208.2.2 Events Perspective 2228.2.3 Affiliation Network with Bridge Organizations X B G20b 2238.3 Formal Concept Analysis 2248.4 Formal Concepts and Galois Derivations 2258.4.1 Concepts in the G20 Affiliation Network 2268.5 Concept Lattice and Ordering of Concepts 2288.5.1 Partial Ordering of the Concepts 2288.5.2 Concept Lattice of the Context 2288.5.3 Concept Lattice of Network X B G20 2308.6 Order Filters and Order Ideals 2328.6.1 Principal Order Filters 2328.6.2 Order Ideals and Principal Order Ideals 2338.7 Affiliation Networks: Summary 2348.8 Learning Affiliation Networks by Doing 2358.8.1 G20 Affiliation Network 2358.8.2 Bipartite Graphs in X B G20 2358.8.3 Co-affiliation Network of G20 Network 2368.8.4 Positional System of X B G20b with Events Classes 2368.8.5 Clustered Bipartite Graph and Binomial Projection of X B G20b 2388.8.6 Formal Concept Analysis 2388.8.7 Order Filters and Order Ideals 2409 Valued Networks 2419.1 Relational Structure of Valued Networks 2429.1.1 Valued Paths in the G20 Trade Network 2429.1.2 Constructing Valued Paths 2459.1.3 Semigroup and Equations of Valued Relations 2469.1.4 First Letter Law in Semigroup Structure 2479.2 Many-valued Contexts 2499.2.1 Conceptual Scaling 2499.2.2 Conceptual Scaling of X B G20 2509.2.3 Concept Lattices Concept lattices of Many-valued Contexts 2539.3 Pathfinder Network Analysis 2559.3.1 Pathfinder Semiring Pathfinder semiring 2569.3.2 Pathfinder Algorithm 2579.4 Pathfinder Semiring to Co-affiliation Network in X B G20 2589.5 Triangle Inequality 2599.5.1 Application of Triangle Inequality triangle inequality to a Valued Configuration 2609.5.2 Triangle Inequality triangle inequality in Multiplex Networks 2619.6 Trade Network X V G20 with Triangle Inequality 2629.7 Valued Networks: Summary 2649.8 Learning Valued Networks by Doing 2659.8.1 Valued Network 2659.8.2 Semigroup of Valued Network with max-min Product 2669.8.3 Many-valued Contexts 2679.8.4 Pathfinder Semiring 2699.8.5 Triangle Inequality 27110 Multilevel Networks 27310.1 Structural Analysis of Multilevel Systems 27310.2 Visual Representation of Clients and Attorneys Multilevel Network 27410.2.1 Additional Features 27610.3 Multilevel Structure of the G20 Network 27610.3.1 Multilevel structure of all G20 countries X M G20 27610.4 Multilevel Positional System of G20 Network with Bridges 27910.4.1 Visual Interpretation of the Multilevel Structure in X B G20b 28010.4.2 Positional Analysis of X M G20b 28210.4.3 Depiction of Multilevel Positional System SM G20b 28310.5 Algebraic Approaches to Multilevel Networks 28410.5.1 G20 Multilevel Network 28510.5.2 Visualization of Multilevel Network Algebra 28710.5.3 Substantial Interpretation 28910.6 Reducing Complexity in X M G20b 28910.7 Further Algebraic Representations of Multilevel Structures 29110.8 Multilevel Networks: Summary 29210.9 Learning Multilevel Networks by Doing 29310.9.1 Multilevel Network ‘Clients and Attorneys’ 29310.9.2 Multilevel Structure of G20 Network with Bridges 29410.9.3 Multilevel Structure of G20 Trade and Affiliation Networks 29510.9.4 Positional System for the Algebraic Analysis 29610.9.5 Relational Structure of Multilevel Configurations 29710.9.6 Two-class Multilevel Positional System 29911 Comparing Relational Structures 30111.1 Comparing Structures with Algebraic Constraints 30211.2 Incubator Networks B and C 30311.2.1 Positional Analysis of XB and XC 30311.3 Equality 30711.3.1 Set of Equations in Incubator Role Structures 30711.4 Hierarchy of Relations 31011.4.1 Set of Inclusions in Incubator Networks 31111.5 Shared Structure by Role Tables 31211.5.1 Lattice of Homomorphisms of the Semigroup 31211.5.2 Joint Homomorphic Reduction, JNTHOM 31411.5.3 Common Structure Semigroup, CSS 31411.5.4 What Constitutes a “Shared” Structure? 31511.6 Semigroup Tables with Joint Homomorphic Reduction 31611.6.1 JNTHOM of Aggregated Role tables QA 31611.6.2 JNTHOM of Aggregated Role tables QB and QC 31711.6.3 Joint Table for Incubator Networks 31811.7 Comparison Across Networks with Common Structure Semigroup 31911.7.1 CSS for Incubator networks A, B, and C 32111.7.2 CSS Order Role Structure for QA−B−C 32411.8 Comparing Structures in Substantial Terms 32411.8.1 Hierarchy of Social Relations and Actor Attributes 32411.8.2 Set of Equations or Equality in QA, QB, and QC 32711.9 Structuring Effect of Role Relations in Incubators 32711.10 Comparing Relational Structures: Summary 32911.11 Learning Comparing Relational Structures by Doing 33011.11.1 Visualization of Incubator Networks B and C 33011.11.2 Positional Analysis and Role Structure for XB and XC 33011.11.3 Decomposition of QB and QC 33111.11.4 Equalities in Incubator Networks 333A Datasets 335Kariera kinship 335Incubators A, B, C 335Florentine families 336Clients and attorneys 336Group of twenty 336B Role structures of Incubator networks 339Role Structure of XA 339Role Structure of XB 339Positional system of Incubator network B 339Role tables in QB 341Role Structure of XC 342Positional system of Incubator network C 342C Valued data in G20 Trade network 347Group of Twenty Indicators 347Commodities in G20 Trade valued network 348Units of measure of G20 country data 348G20 Trade valued network and salient structures 348D Layout visualization algorithms 353Force-directed 353Stress-majorization 355Laplacian Function 358New stress internal function 359E Role structure workflow 361Decomposition of Role structure QB 361Incubator network B 361Positional analysis and Role structure 361Factorization 362Progressive factorization of Factors 363Aggregated structure of QB 370Bibliography 371Index 377