Generalized Blockmodeling

by Patrick Doreian , Vladimir Batagelj , Anuska Ferligoj

• ISBN13: 9780521840859
• ISBN10: 0521840856
• Format: Hardcover
• Copyright: 2004-11-08
• Publisher: Cambridge University Press

Summary

This book provides an integrated treatment of blockmodeling, the most frequently used technique in social network analysis. It secures its mathematical foundations and then generalizes blockmodeling for the analysis of many types of network structures. Examples are used throughout the text and include small group structures, little league baseball teams, intra-organizational networks, inter-organizational networks, baboon grooming networks, marriage ties of noble families, trust networks, signed networks, Supreme Court decisions, journal citation networks, and alliance networks. Also provided is an integrated treatment of algebraic and graph theoretic concepts for network analysis and a broad introduction to cluster analysis. These formal ideas are the foundations for the authors' proposal for direct optimizational approaches to blockmodeling which yield blockmodels that best fit the data, a measure of fit that is integral to the establishment of blockmodels, and creates the potential for many generalizations and a deductive use of blockmodeling.

Table of Contents

Preface	xiii
1 Social Networks and Blockmodels	1	(29)
1.1 An Intuitive Statement of Network Ideas	3	(8)
1.1.1 Fundamental Types of Social Relations	5	(6)
1.1.2 Types of Relational Data Arrays	11	(1)
1.2 Blocks as Parts of Networks	11	(3)
1.2.1 Blocks	12	(2)
1.3 Some Block Types	14	(2)
1.4 Specifying Blockmodels	16	(8)
1.4.1 Parent-Child Role Systems	16	(1)
1.4.2 Organizational Hierarchies	17	(2)
1.4.3 Systems of Ranked Clusters	19	(1)
1.4.4 Baboon Grooming Networks	20	(4)
1.5 Conventional Blockmodeling	24	(1)
1.5.1 Equivalence and Blockmodeling	24	(1)
1.6 Generalized Blockmodeling	25	(2)
1.7 An Outline Map of the Topics Considered	27	(3)
2 Network Data Sets	30	(34)
2.1 Classic Data Sets	30	(17)
2.1.1 Sampson Monastery Data	31	(6)
2.1.2 Bank Wiring Room Data	37	(7)
2.1.3 Newcomb Fraternity Data	44	(3)
2.2 Newer Data Sets	47	(14)
2.2.1 Little League Baseball Teams	47	(3)
2.2.2 Political Actor Network	50	(2)
2.2.3 Student Government Data	52	(2)
2.2.4 Kansas Search and Rescue Network	54	(2)
2.2.5 A Bales-Type Group Dynamics Network	56	(1)
2.2.6 Ragusan Families Marriage Networks	56	(4)
2.2.7 Two Baboon Grooming Networks	60	(1)
2.3 Data Set Properties	61	(2)
2.4 Some Additional Remarks Concerning Data	63	(1)
3 Mathematical Prelude	64	(30)
3.1 Basic Set Theory	64	(6)
3.2 Relations	70	(14)
3.2.1 Operations with Binary Relations	74	(2)
3.2.2 Comparing Relations	76	(4)
3.2.3 Special Operations	80	(4)
3.3 Functions	84	(5)
3.3.1 Products of Functions	87	(1)
3.3.2 Relational Homomorphisms	88	(1)
3.4 Basic Algebra	89	(4)
3.5 Transitions to Chapters 4 and 9	93	(1)
4 Relations and Graphs for Network Analysis	94	(39)
4.1 Graphs	94	(18)
4.1.1 Examples of Graphs	104	(3)
4.1.2 Traveling on a Graph	107	(4)
4.1.3 Graph Coloring	111	(1)
4.2 Types of Binary Relations	112	(5)
4.2.1 Properties of Relations	113	(1)
4.2.2 Closures	114	(1)
4.2.3 Computing the Transitive Closure	115	(1)
4.2.4 Special Elements	116	(1)
4.2.5 Tournaments	117	(1)
4.3 Partitions and Equivalence Relations	117	(5)
4.4 Acyclic Relations	122	(2)
4.4.1 Levels	123	(1)
4.5 Orders	124	(3)
4.5.1 Factorization	125	(1)
4.5.2 Hasse Diagram	126	(1)
4.5.3 Numberings	127	(1)
4.6 Networks	127	(1)
4.7 Centrality in Networks	128	(3)
4.7.1 Algorithmic Aspects	131	(1)
4.8 Summary and Transition	131	(2)
5 Clustering Approaches	133	(35)
5.1 An Introduction to Cluster Analytic Ideas	133	(1)
5.2 Usual Clustering Problems	134	(3)
5.2.1 An Example	135	(2)
5.2.2 The Usual Steps of Solving Clustering Problems	137	(1)
5.3 (Dis)similarities	137	(6)
5.3.1 (Dis)similarity Measures for Numerical Data	138	(4)
5.3.2 (Dis)similarity Measures for Binary Data	142	(1)
5.4 Clustering Algorithms	143	(7)
5.4.1 The Hierarchical Approach	144	(5)
5.4.2 The Leader Algorithm	149	(1)
5.4.3 The Relocation Algorithms	150	(1)
5.5 Constrained Clustering	150	(10)
5.5.1 The Constrained Clustering Problem	151	(3)
5.5.2 Solving Constrained Clustering Problems	154	(2)
5.5.3 The Structure Enforcement Coefficient	156	(1)
5.5.4 An Empirical Example	156	(4)
5.6 Multicriteria Clustering	160	(7)
5.6.1 A Multicriteria Clustering Problem	160	(1)
5.6.2 Solving Discrete Multicriteria Optimization Problems	161	(1)
5.6.3 Direct Multicriteria Clustering Algorithms	161	(3)
5.6.4 An Example	164	(3)
5.7 Transition to Blockmodeling	167	(1)
6 An Optimizational Approach to Conventional Blockmodeling	168	(42)
6.1 Conventional Blockmodeling	168	(16)
6.1.1 Definitions of Equivalences	170	(6)
6.1.2 Equivalence and k-Partite Graphs	176	(1)
6.1.3 Establishing Conventional Blockmodels	176	(1)
6.1.4 The Indirect Blockmodeling Approach	177	(1)
6.1.5 Measuring the Equivalence of Pairs of Units	178	(6)
6.2 Optimization and Blockmodeling	184	(8)
6.2.1 The Direct Blockmodeling Approach	185	(1)
6.2.2 A Criterion for Structural Equivalence	186	(1)
6.2.3 A Criterion for Regular Equivalence	187	(1)
6.2.4 A Clustering Algorithm	188	(1)
6.2.5 Two Artificial Examples	188	(4)
6.3 Representing Partitions	192	(4)
6.4 Some Empirical Examples	196	(7)
6.4.1 Two Little League Baseball Teams	196	(5)
6.4.2 The Political Actor Example	201	(2)
6.5 An Analysis of a Search and Rescue Operation	203	(6)
6.6 Generalized Blockmodeling	209	(1)
7 Foundations for Generalized Blockmodeling	210	(37)
7.1 Generalization of Equivalences	211	(9)
7.1.1 Some Properties of the Predicates	213	(2)
7.1.2 Examples	215	(5)
7.2 Generalized Blockmodeling	220	(7)
7.2.1 Blockmodels	220	(2)
7.2.2 Τ-Equivalence	222	(1)
7.2.3 Optimization	223	(4)
7.3 Two Examples of Generalized Blockmodeling	227	(6)
7.3.1 An Artificial Network	227	(1)
7.3.2 A Student Government Network	228	(3)
7.3.3 Exploring Multiple Partitions	231	(2)
7.4 Prespecified Blockmodels	233	(2)
7.5 Blockmodel Types	235	(2)
7.6 Applications of Prespecified Blockmodels	237	(8)
7.6.1 Classroom Liking Ties for Boys and Girls	237	(1)
7.6.2 Baboon Grooming Networks	238	(5)
7.6.3 Multiple Blockmodels and Inconsistencies	243	(2)
7.7 Some Benefits of the Optimization Approach	245	(1)
7.8 Extending Generalized Blockmodeling	245	(2)
8 Blockmodeling Two-Mode Network Data	247	(24)
8.1 Two-Mode Network Data	247	(1)
8.2 Approaches to Two-Mode Network Data	248	(1)
8.3 Blockmodels for Two-Mode Network Data	249	(1)
8.4 A Formalization of Blockmodeling Two-Mode Data	250	(1)
8.5 Blockmodels with Empirical Data	251	(19)
8.5.1 Supreme Court Voting	251	(6)
8.5.2 The Southern Women Event Participation Data	257	(8)
8.5.3 Journal-to-Journal Citation Networks	265	(5)
8.6 Summary	270	(1)
9 Semirings and Lattices	271	(24)
9.1 Walks, Paths, and Algebras	271	(2)
9.2 Distributivity and Absorption	273	(1)
9.2.1 Distributivity	274	(1)
9.2.2 Absorption	274	(1)
9.3 Valued Graphs	274	(5)
9.3.1 Assigning Values to Paths	275	(1)
9.3.2 Assessing Paths in Terms of Their Values	276	(3)
9.4 Semirings	279	(6)
9.4.1 Some Social Network Applications of Semirings	282	(3)
9.5 Semilattices and Lattices as Relations	285	(5)
9.5.1 Bounds	286	(1)
9.5.2 Semilattices and Lattices	287	(3)
9.6 Algebraic View on Lattices	290	(4)
9.6.1 Types of Lattices	291	(2)
9.6.2 Representations	293	(1)
9.7 Conclusion	294	(1)
10 Balance Theory and Blockmodeling Signed Networks	295	(31)
10.1 Structural Balance Theory	296	(1)
10.2 Signed Networks	297	(2)
10.3 Partitioning Signed Networks and Semirings	299	(3)
10.3.1 Examples	301	(1)
10.4 A Partitioning Algorithm for Signed Networks	302	(2)
10.5 Exactly kappa-Balanced Structures	304	(3)
10.5.1 An Empirical Example	306	(1)
10.6 Structures That are Not k-Balanced	307	(3)
10.6.1 A Constructed Example	307	(1)
10.6.2 An Empirical Example	307	(3)
10.7 Another Look at the Bank Wiring Room Data	310	(2)
10.8 Balance and Imbalance in a Bales Group	312	(5)
10.9 Through-Time Balance Processes	317	(29)
10.9.1 The Sampson Data	318	(2)
10.9.2 The Newcomb Data	320	(4)
10.10 Blockmodeling and Signed Networks	324	(2)
11 Symmetric-Acyclic Blockmodels	326	(21)
11.1 Blocks for Directed Graphs and Acyclic Graphs	326	(1)
11.2 Two Constructed Examples	327	(1)
11.3 Establishing Symmetric-Acyclic Decompositions of Networks	328	(5)
11.3.1 Ideal Structures	328	(3)
11.3.2 Relations without a Symmetric-Acyclic Decomposition	331	(2)
11.4 Liking Ties for Children in a Classroom	333	(4)
11.5 The Student Government Example	337	(2)
11.5.1 A Hypothesized Blockmodel	337	(1)
11.5.2 A Second Hypothesized Blockmodel	338	(1)
11.6 A Return to the Classroom Example	339	(1)
11.7 Marriage Network of the Ragusan Noble Families	340	(6)
11.7.1 Network Decomposition	341	(3)
11.7.2 Blockmodeling Approach	344	(2)
11.8 Discussion	346	(1)
12 Extending Generalized Blockmodeling	347	(16)
12.1 Block Types	347	(1)
12.2 Block Types and Criterion Functions	348	(1)
12.3 Using Substantive and Empirical Knowledge	349	(1)
12.3.1 Prespecification	349	(1)
12.3.2 Constraints	350	(1)
12.3.3 Imposing Penalties	350	(1)
12.4 The Magnitudes of Criterion Functions	350	(2)
12.5 The Generalized Blockmodeling Framework	352	(2)
12.6 Composition of Blocks	354	(1)
12.7 Multiple Fitted Blockmodels	355	(1)
12.8 Multiple Relations	356	(2)
12.9 Other Networks and Network Types	358	(2)
12.10 Network Size and Valued Graphs	360	(3)
Bibliography	363	(12)
Author Index	375	(3)
Subject Index	378