A puzzle concerning triads in social networks: Graph constraints and the triad census

Evidence from many sources shows that triadic tendencies are important structural features of social networks (e.g. transitivity or triadic closure) and triadic configurations are the basis for both theoretical claims and substantive outcomes (e.g. strength of weak ties, tie stability, or trust). A contrasting line of research demonstrates that triads in empirical social networks are well predicted by lower order graph features (density and dyads), accounting for around 90% of the variability in triad distributions when comparing different social networks (Faust, 2006, 2007, 2008). These two sets of results present a puzzle: how can substantial triadic tendencies occur when triads in empirical social networks are largely explained by lower order graph features? This paper provides insight into the puzzle by considering constraints that lower order graph features place on the triad census. Taking a comparative perspective, it shows that triad censuses from 159 social networks of diverse species and social relations are largely explained by their lower order graph features (the dyad census) through formal constraints that force triads to occur in narrow range of configurations. Nevertheless, within these constraints, a majority of networks exhibit significant triadic patterning by departing from expectation.     

VERY LOCAL STRUCTURE IN SOCIAL NETWORKS

Triadic configurations are fundamental to many social structural processes and provide the basis for a variety of social network theories and methodologies. This paper addresses the question of how much of the patterning of triads is accounted for by lower-order properties pertaining to nodes and dyads. The empirical base is a collection of 82 social networks representing a number of different species (humans, baboons, macaques, bison, cattle, goats, sparrows, caribou, and more) and an assortment of social relations (friendship, negative sentiments, choice of work partners, advice seeking, reported social interactions, victories in agonistic encounters, dominance, and co-observation). Methodology uses low dimensional representations of triad censuses for these social networks, as compared to censuses expected given four lower-order social network properties. Results show that triadic structure is largely accounted for by properties more local than triads: network density, nodal indegree and outdegree distributions, and the dyad census. These findings reinforce the observation that structural configurations that can be realized in empirical social networks are severely constrained by very local network properties, making some configurations extremely improbable.     

Social context,spatial structure and social network structure

Frequently, social networks are studied in their own right with analyses devoid of contextual details. Yet contextual features – both social and spatial – can have impacts on the networks formed within them. This idea is explored with five empirical networks representing different contexts and the use of distinct modeling strategies. These strategies include network visualizations, QAP regression, exponential random graph models, blockmodeling and a combination of blockmodels with exponential random graph models within a single framework. We start with two empirical examples of networks inside organizations. The familiar Bank Wiring Room data show that the social organization (social context) and spatial arrangement of the room help account for the social relations formed there. The second example comes from a police academy where two designed arrangements, one social and one spatial, powerfully determine the relational social structures formed by recruits. The next example is an inter-organizational network that emerged as part of a response to a natural disaster where features of the improvised context helped account for the relations that formed between organizations participating in the search and rescue mission. We then consider an anthropological example of signed relations among sub-tribes in the New Guinea highlands where the physical geography is fixed. This is followed by a trading network off the Dalmatian coast where geography and physical conditions matter. Through these examples, we show that context matters by shaping the structure of networks that form and that a variety of network analytic tools can be mobilized to reveal how networks are shaped, in part, by social and spatial contexts. Implications for studying social networks are suggested.     

Sampling and estimation in large social networks

An unknown network is modelled by a directed or undirected graph having vertices of different kinds. Partial information is available concerning the vertex labels and the edge occurrences within a simple random sample of vertices. Using this information we find unbiased estimators and variance estimators of such graph parameters which can be given as dyad or triad counts. In particular, we give approximate formulae pertaining to large networks.     

An introduction to exponential random graph (p) models for social networks

This article provides an introductory summary to the formulation and application of exponential random graph models for social networks. The possible ties among nodes of a network are regarded as random variables, and assumptions about dependencies among these random tie variables determine the general form of the exponential random graph model for the network. Examples of different dependence assumptions and their associated models are given, including Bernoulli, dyad-independent and Markov random graph models. The incorporation of actor attributes in social selection models is also reviewed. Newer, more complex dependence assumptions are briefly outlined. Estimation procedures are discussed, including new methods for Monte Carlo maximum likelihood estimation. We foreshadow the discussion taken up in other papers in this special edition: that the homogeneous Markov random graph models of Frank and Strauss [Frank, O., Strauss, D., 1986. Markov graphs. Journal of the American Statistical Association 81, 832–842] are not appropriate for many observed networks, whereas the new model specifications of Snijders et al. [Snijders, T.A.B., Pattison, P., Robins, G.L., Handock, M. New specifications for exponential random graph models. Sociological Methodology, in press] offer substantial improvement.     

Closure,connectivity and degree distributions: Exponential random graph (p*) models for directed social networks

The new higher order specifications for exponential random graph models introduced by Snijders et al. [Snijders, T.A.B., Pattison, P.E., Robins G.L., Handcock, M., 2006. New specifications for exponential random graph models. Sociological Methodology 36, 99–153] exhibit substantial improvements in model fit compared with the commonly used Markov random graph models. Snijders et al., however, concentrated on non-directed graphs, with only limited extensions to directed graphs. In particular, they presented a transitive closure parameter based on path shortening. In this paper, we explain the theoretical and empirical advantages in generalizing to additional closure effects. We propose three new triadic-based parameters to represent different versions of triadic closure: cyclic effects; transitivity based on shared choices of partners; and transitivity based on shared popularity. We interpret the last two effects as forms of structural homophily, where ties emerge because nodes share a form of localized structural equivalence. We show that, for some datasets, the path shortening parameter is insufficient for practical modeling, whereas the structural homophily parameters can produce useful models with distinctive interpretations. We also introduce corresponding lower order effects for multiple two-path connectivity. We show by example that the in- and out-degree distributions may be better modeled when star-based parameters are supplemented with parameters for the number of isolated nodes, sources (nodes with zero in-degrees) and sinks (nodes with zero out-degrees). Inclusion of a Markov mixed star parameter may also help model the correlation between in- and out-degrees. We select some 50 graph features to be investigated in goodness of fit diagnostics, covering a variety of important network properties including density, reciprocity, geodesic distributions, degree distributions, and various forms of closure. As empirical illustrations, we develop models for two sets of organizational network data: a trust network within a training group, and a work difficulty network within a government instrumentality.     

Microstructural analysis in interorganizational systems

This paper argues that network analyses of interorganizational relations should begin by examining the way in which relations are organized at the local level. It posits that systematic departures from random models for dyad and triad censuses should be found before interpreting structural patterns isolated by analytic techniques concerned with overall network structure. Three principles of organizational bonding (resource inequality, reciprocity, and redundancy) are identified, and the implications of these for dyadic and triadic microstructures are detailed. Particular attention is given to differentiating between microstructural patterns to be anticipated when a system consists of autonomous actors approximately equal in power and resources and those expected when a system is highly centralized.     

Networks and geography: Modelling community network structures as the outcome of both spatial and network processes

This paper focuses on how to extend the exponential random graph models to take into account the geographical embeddedness of individuals in modelling social networks. We develop a hierarchical set of nested models for spatially embedded social networks, in which, following Butts (2002), an interaction function between tie probability and Euclidean distance between nodes is introduced. The models are illustrated by an empirical example from a study of the role of social networks in understanding spatial clustering in unemployment in Australia. The analysis suggests that a spatial effect cannot solely explain the emergence of organised network structure and it is necessary to include both spatial and endogenous network effects in the model.     

Catching up with big fish in the big pond? Multi-level network analysis through linked design

This article contributes to the study of “duality” [Breiger, R., 1974. The duality of persons and groups. Social Forces 53, 181–190] in social life. Our study explores multi-level networks of superposed and partially connected interdependencies, the first being inter-organizational, the second inter-individual. We propose a method of structural linked design as an articulation for these levels. First, we examine separately the complete networks at each level. Second, we combine the two networks in relation to one another using systematic information about the membership of each individual in the first network (inter-individual) to one of the organizations in the second network (inter-organizational), as in bipartite networks. This dual positioning, or the linked design approach, is carried out in an empirical study examining performance variations within the “elite” of French cancer researchers in 1999. By looking at measures of centrality, we identify the actors that these top researchers consider as central or peripheral at the inter-individual level (the big and the little fish among the elite), and the laboratories that the research directors consider as central or peripheral at the inter-organizational level (the big and the little ponds among all the laboratories conducting cancer research in France at that time). In addition to the rather trivial report of the competitive advantage of big fish in big ponds (particularly because of the advantage of size for laboratories in this field), we use measurements of scientific performance to identify “catching up” strategies that the smallest fish use in this system. We suggest that this method offers new insights into the duality and multi-level dimension of complex systems of interdependencies, and also into the ways in which actors manage these interdependencies. We believe that it adds a new dimension to the sociological exploration of the determinants of performance, of meso-level phenomena such as opportunity structures and institutional change, or of macro-level phenomena such as social inequalities.     

The Cohesiveness of Blocks In Social Networks: Node Connectivity and Conditional Density

This study shows several ways that formal graph theoretic statements map patterns of network ties into substantive hypotheses about social cohesion. If network cohesion is enhanced by multiple connections between members of a group, for example, then the higher the global minimum of the number of independent paths that connect every pair of nodes in the network, the higher the social cohesion. The cohesiveness of a group is also measured by the extent to which it is not disconnected by removal of 1, 2, 3,..., k actors. Menger's Theorem proves that these two measures are equivalent. Within this graph theoretic framework, we evaluate various concepts of cohesion and establish the validity of a pair of related measures: 1. Connectivity—the minimum number k of its actors whose removal would not allow the group to remain connected or would reduce the group to but a single member—measures the social cohesion of a group at a general level. 2. Conditional density measures cohesion on a finer scale as a proportion of ties beyond that required for connectivity k over the number of ties that would force it to k + 1.
Calibrated for successive values of k, these two measures combine into an aggregate measure of social cohesion, suitable for both small- and large-scale network studies. Using these measures to define the core of a new methodology of cohesive blocking, we offer hypotheses about the consequences of cohesive blocks for social groups and their members, and explore empirical examples that illustrate the significance, theoretical relevance, and predictiveness of cohesive blocking in a variety of substantively important applications in sociology.     

Measuring social dynamics in a massive multiplayer online game

Quantification of human group-behavior has so far defied an empirical, falsifiable approach. This is due to tremendous difficulties in data acquisition of social systems. Massive multiplayer online games (MMOG) provide a fascinating new way of observing hundreds of thousands of simultaneously socially interacting individuals engaged in virtual economic activities. We have compiled a data set consisting of practically all actions of all players over a period of 3 years from a MMOG played by 300,000 people. This large-scale data set of a socio-economic unit contains all social and economic data from a single and coherent source. Players have to generate a virtual income through economic activities to ‘survive’ and are typically engaged in a multitude of social activities offered within the game. Our analysis of high-frequency log files focuses on three types of social networks, and tests a series of social-dynamics hypotheses. In particular we study the structure and dynamics of friend-, enemy- and communication networks. We find striking differences in topological structure between positive (friend) and negative (enemy) tie networks. All networks confirm the recently observed phenomenon of network densification. We propose two approximate social laws in communication networks, the first expressing betweenness centrality as the inverse square of the overlap, the second relating communication strength to the cube of the overlap. These empirical laws provide strong quantitative evidence for the Weak ties hypothesis of Granovetter. Further, the analysis of triad significance profiles validates well-established assertions from social balance theory. We find overrepresentation (underrepresentation) of complete (incomplete) triads in networks of positive ties, and vice versa for networks of negative ties. Empirical transition probabilities between triad classes provide evidence for triadic closure with extraordinarily high precision. For the first time we provide empirical results for large-scale networks of negative social ties. Whenever possible we compare our findings with data from non-virtual human groups and provide further evidence that online game communities serve as a valid model for a wide class of human societies. With this setup we demonstrate the feasibility for establishing a ‘socio-economic laboratory’ which allows to operate at levels of precision approaching those of the natural sciences.All data used in this study is fully anonymized; the authors have the written consent to publish from the legal department of the Medical University of Vienna.     

A comparative study of social network models: Network evolution models and nodal attribute models

This paper reviews, classifies and compares recent models for social networks that have mainly been published within the physics-oriented complex networks literature. The models fall into two categories: those in which the addition of new links is dependent on the (typically local) network structure (network evolution models, NEMs), and those in which links are generated based only on nodal attributes (nodal attribute models, NAMs). An exponential random graph model (ERGM) with structural dependencies is included for comparison. We fit models from each of these categories to two empirical acquaintance networks with respect to basic network properties. We compare higher order structures in the resulting networks with those in the data, with the aim of determining which models produce the most realistic network structure with respect to degree distributions, assortativity, clustering spectra, geodesic path distributions, and community structure (subgroups with dense internal connections). We find that the nodal attribute models successfully produce assortative networks and very clear community structure. However, they generate unrealistic clustering spectra and peaked degree distributions that do not match empirical data on large social networks. On the other hand, many of the network evolution models produce degree distributions and clustering spectra that agree more closely with data. They also generate assortative networks and community structure, although often not to the same extent as in the data. The ERGM model, which turned out to be near-degenerate in the parameter region best fitting our data, produces the weakest community structure.     

A message-focused measurement of the communication dimension of social capital: Revealing shared meaning in a network of relationships

This study integrates two theoretically driven methods—network analysis and fantasy theme analysis—to present a message-focused operationalization for the communication dimension of social capital. The results find empirical support for scholars’ theorizing that public relations-facilitated messages cultivate shared meaning and foster social capital. The relationship between shared meaning and social capital was especially evident in network subgroups (cliques). This article contributes to social capital theory building by focusing on the meaning making process that strengthens social capital in networks. Public relations practitioners’ communicative roles in social capital cultivation are made evident with a message-focused measurement.     

Do Social Networks Really Matter in Contentious Politics?

A considerable number of studies in the social movement literature stress that social networks are a key factor for those participating in political protest. However, since empirical evidence does not universally support this thesis, we propose to examine three core questions. Do networks really matter for participants in political protest? Are social networks important for all types of protest? Finally, what are social networks and in which ways are they important? By answering these questions this paper aims to provide three contributions to social movement literature: first, we want to put networks in their place and not reifying their influence on participation processes; second, we describe and explain variations of networks influence on protest participation; third, to pursue the theoretical reflection initiated by Kitts, McAdam, and Passy on the specification of network effect on contentious participation, that is, to disentangle the different processes at stake. Many scholars argue for empirical works analyzing the link between networks and cognition, but this remains a pious wish. Here, we propose to systematically examine the effect of social interactions on activists' cognitive toolkit.     

Univariate and multivariate models of positive and negative networks: Liking,disliking, and bully–victim relationships

Three relations between elementary school children were investigated: networks of general dislike and bullying were related to networks of general like. These were modeled using multivariate cross-sectional (statistical) network models. Exponential random graph models for a sample of 18 classrooms, numbering 393 students, were summarized using meta-analyses. Results showed (balanced) network structures with positive ties between those who were structurally equivalent in the negative network. Moreover, essential structural parameters for the univariate network structure of positive (general like) and negative (general dislike and bullying) tie networks were identified. Different structures emerged in positive and negative networks. The results provide a starting point for further theoretical and (multiplex) empirical research about negative ties and their interplay with positive ties.     

A representation for the Mexican political networks

A compressed graph representation for use with the Mexican political networks is introduced. Properties of these graphs are investigated. It is also explained how the Jorge–Schmidt power centrality index can be used to index the centrality of nodes in the original network from the compressed graph representation.     

Balance in stochastic signed graphs

Signed graphs provide models for investigating balance in connection with various kinds of social relations. Since empirical social networks always involve uncertainty because of errors due to measurement, imperfect observation or sampling, it is desirable to incorporate uncertainty into signed graph models. We introduce a stochastic signed graph and investigate the properties of some indices of balance involving triads. In particular we consider the balance properties of a graph which is randomly signed and of one which has been randomly sampled from a large population graph.     

Jaccard-Spline index of structural proximity in contact networks

Network analysts are increasingly being called upon to apply their expertise to groups for which the only available or reliable data is a contact network. With no opportunity to gather additional data, the merits of such applications depend on empirical studies that validate the employment of structural constructs based on contact networks. Fortunately, we possess such studies in abundance. One of the strongest research traditions in social network analysis is the development of formal constructs that may be employed in analyses of networks. I suggest that greater insight into predictive success of network constructs may be acquired by addressing the following question: what features of the contact network in which a dyad is situated allow the prediction of other relations with an accuracy that validates the imputation of the latter given data on the former? In this article, I present findings on the structural contexts of dyads in contact networks and the relationship of these contexts with two fundamental forms of cohesive cognitive relations—accorded interpersonal influence and perceived interpersonal agreement. Based on these findings, I formalize a measure of structural proximity in contact networks with values that correspond to the conditional probabilities of these two forms of cohesive cognitive relations. The substantive settings of this analysis are policy groups with members who are embedded in contact structures based on regular interpersonal communication on policy issues and cognitive structures based on perceived interpersonal agreement and accorded interpersonal influence.     

NEW SPECIFICATIONS FOR EXPONENTIAL RANDOM GRAPH MODELS

The most promising class of statistical models for expressing structural properties of social networks observed at one moment in time is the class of exponential random graph models (ERGMs), also known as p * models. The strong point of these models is that they can represent a variety of structural tendencies, such as transitivity, that define complicated dependence patterns not easily modeled by more basic probability models. Recently, Markov chain Monte Carlo (MCMC) algorithms have been developed that produce approximate maximum likelihood estimators. Applying these models in their traditional specification to observed network data often has led to problems, however, which can be traced back to the fact that important parts of the parameter space correspond to nearly degenerate distributions, which may lead to convergence problems of estimation algorithms, and a poor fit to empirical data.
This paper proposes new specifications of exponential random graph models. These specifications represent structural properties such as transitivity and heterogeneity of degrees by more complicated graph statistics than the traditional star and triangle counts. Three kinds of statistics are proposed: geometrically weighted degree distributions, alternating k -triangles, and alternating independent two-paths. Examples are presented both of modeling graphs and digraphs, in which the new specifications lead to much better results than the earlier existing specifications of the ERGM. It is concluded that the new specifications increase the range and applicability of the ERGM as a tool for the statistical analysis of social networks.