Partitioning signed social networks

Structural balance theory has proven useful for delineating the blockmodel structure of signed social networks. Even so, most of the observed signed networks are not perfectly balanced. One possibility for this is that in examining the dynamics underlying the generation of signed social networks, insufficient attention has been given to other processes and features of signed networks. These include: actors who have positive ties to pairs of actors linked by a negative relation or who belong to two mutually hostile subgroups; some actors that are viewed positively across the network despite the presence of negative ties and subsets of actors with negative ties towards each other. We suggest that instead viewing these situations as violations of structural balance, they can be seen as belonging to other relevant processes we call mediation, differential popularity and internal subgroup hostility. Formalizing these ideas leads to the relaxed structural balance blockmodel as a proper generalization of structural balance blockmodels. Some formal properties concerning the relation between these two models are presented along with the properties of the fitting method proposed for the new blockmodel type. The new method is applied to four empirical data sets where improved fits with more nuanced interpretations are obtained.     

Event sequences as generators of social network evolution

The argument presented in this paper is that one fruitful approach to the study of social network evolution takes the form of examining event sequences as generating mechanisms. Evidence for this comes from two empirical studies of structural balance theory and one simulation study of balance theoretic processes. Four views of causality—system, statistical (predictive), mechanism and algorithmic—are briefly contrasted and then examined with structural balance theory in mind. The conventional statement of the theory turns out to be under specified and inattentive to alternative mechanisms that can generate signed networks through time. Empirical studies of structural balance are limited with regard to the kinds of data that are usually collected. Proposals for studying the generation of signed networks through event sequences while being attentive to structural balance ideas are presented.     

Structural holes and bridging in two-mode networks

Social networks are often structured in such a way that there are gaps, or “structural holes,” between regions. Some actors are in the position to bridge or span these gaps, giving rise to individual advantages relating to brokerage, gatekeeping, access to non-redundant contacts, and control over network flows. The most widely used measures of a given actor’s bridging potential gauge the extent to which that actor is directly connected to others who are otherwise not well connected to each other. Unfortunately, the measures that have been developed to identify structural holes cannot be adapted directly to two-mode networks, like individual-to-organization networks. In two-mode networks, direct contacts cannot be directly connected to each other by definition, making the calculation of redundancy, effective size, and constraint impossible with conventional one-mode methods. We therefore describe a new framework for the measurement of bridging in two-mode networks that hinges on the mathematical concept of the intersection of sets. An actor in a given node class (“ego”) has bridging potential to the extent that s/he is connected to actors in the opposite node class that have unique profiles of connections to actors in ego’s own node class. We review the relevant literature pertaining to structural holes in two-mode networks, and we compare our primary bridging measure (effective size) to measures of bridging that result when using one-mode projections of two-mode data. We demonstrate the results of applying our approach to empirical data on the organizational affiliations of elites in a large U.S. city.     

The sign of affection: Balance-theoretic models and incomplete signed digraphs

The initial structural models based on balance theory (structural balance and clusterability) dealt with incomplete signed digraphs. However, newer models (ranked clusters, transitivity, hierarchical M̄-cliques) apply only to zero-one matrices representing either unsigned digraphs or complete signed digraphs. Since empirical networks of affective relations are signed but seldom complete — actors may have neutral feelings towards alters or affections may be unknown to the researcher — the latter models must be redefined if affective relations are to be analysed. It was found that each balance-theoretic model is characterised by a particular type of semicycle or path. Counts of the types of semicycles and paths suffice to identify the models. This approach is more general than triadic analysis because it handles complete as well as incomplete signed digraphs.     

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.     

A partitioning approach to structural balance

The classic formulation of structural balance by Cartwright and Harary (Psychological Review, 63, 1956, 277–293) had the basic structural theorem that a balanced structure could be partitioned into two mutually antagonistic subgroups each having internal solidarity. Davis (Human Relations, 20, 1967, 181–187) extended this theorem for cases where there can be more than two such mutually antagonistic subgroups. We use these theorems to construct a criterion function for a local optimization partitioning procedure for signed digraphs. For any signed digraph, this procedure yields those partitions with the smallest number of errors, a measure of the imbalance in the graph, and an identification of those links inconsistent with both generalized and structural balance. These methods are applied to some artificial data and to the affect data from Sampson (A novitiate in a period of change: An experimental and case study of social relationships, Dissertation, Cornell University, 1968). The latter provides a positive test of a basic tenet of balance theory, that there is a tendency towards balance with signed relations in human groups. While these methods can be applied to all signed digraphs and signed graphs, the balance hypothesis is relevant only for affect ties.     

Network centrality and social movement media coverage: A two-mode network analytic approach

This article examines the relationship between structural location (namely, degree centrality) and news media coverage. Our central hypothesis is that the network centrality of social movement actors is positively associated with the prevalence of actors being cited in the print news media. This paper uses two-mode data from a communication network of environmentalists in British Columbia, and examines the relationship between their structural location and the frequency by which they are cited in newsprint media with regard to particular frames (about forest conservation, environmental protest, and related issues). We asked a sample of social movement participants about their ties to a target list of relatively high profile actors (environmental activists). We turned the resulting network matrix into a bipartite graph that examined the relationships amongst the target actors vis a vis the respondents. Next we calculated point in-degree for the target actors. For the target actors we also have data from a representative sample of 957 print news articles about forestry and conservation of old growth forests in British Columbia. We compare the effects of network centrality of the target actor versus several attributes of the target actors (gender, level of radicalism, leadership status) on the amount of media coverage that each of the target actors receives. We find that network centrality is associated with media coverage controlling for actor attributes. We discuss theoretical implications of this research. Finally, we also discuss the methodological pros and cons of using a “target name roster” to construct two-mode data on social movement activists.     

Triadic closure in two-mode networks: Redefining the global and local clustering coefficients

As the vast majority of network measures are defined for one-mode networks, two-mode networks often have to be projected onto one-mode networks to be analyzed. A number of issues arise in this transformation process, especially when analyzing ties among nodes’ contacts. For example, the values attained by the global and local clustering coefficients on projected random two-mode networks deviate from the expected values in corresponding classical one-mode networks. Moreover, both the local clustering coefficient and constraint (structural holes) are inversely associated to nodes’ two-mode degree. To overcome these issues, this paper proposes redefinitions of the clustering coefficients for two-mode networks.     

Why does everybody hate me? Balance,status, and homophily: The triumvirate of signed tie formation

Despite being one of the foundational theories of signed (positive/negative) tie formation, the evidence for balance theory is far from conclusive. A recent promising alternative is status theory, but a theoretical and explanatory gap still remains, with a dearth of theories and evidence. We put forward and test eight separate theories of signed tie formation on two face-to-face networks of friendship and esteem of 282 students. We use dimension reduction (factor analysis) on the results tables comparing the predictions of these eight theories for 50 ERGM parameters with our estimated models. We find three main paradigms explain the majority of signed network formation: balance, status, and homophily.     

Analyzing event stream dynamics in two-mode networks: An exploratory analysis of private communication in a question and answer community

Information about social networks can often be collected as event stream data. However, most methods in social network analysis are defined for static network snapshots or for panel data. We propose an actor oriented Markov process framework to analyze the structural dynamics in event streams. Estimated parameters are similar to what is known from exponential random graph models or stochastic actor oriented models as implemented in SIENA. We apply the methodology on a question and answer web community and show how the relevance of different kinds of one- and two-mode network structures can be tested using a new software.     

Conditionally exponential random models for individual properties and network structures: Method and application

Exponential random models have been widely adopted as a general probabilistic framework for complex networks and recently extended to embrace broader statistical settings such as dynamic networks, valued networks or two-mode networks. Our aim is to provide a further step into the generalization of this class of models by considering sample spaces which involve both families of networks and nodal properties verifying combinatorial constraints. We propose a class of probabilistic models for the joint distribution of nodal properties (demographic and behavioral characteristics) and network structures (friendship and professional partnership). It results in a general and flexible modeling framework to account for homophily in social structures. We present a Bayesian estimation method based on the full characterization of their sample spaces by systems of linear constraints. This provides an exact simulation scheme to sample from the likelihood, based on linear programming techniques. After a detailed analysis of the proposed statistical methodology, we illustrate our approach with an empirical analysis of co-authorship of journal articles in the field of neuroscience between 2009 and 2013.     

k-means-based algorithm for blockmodeling linked networks

The paper presents a k-means-based algorithm for blockmodeling linked networks where linked networks are defined as a collection of one-mode and two-mode networks in which units from different one-mode networks are connected through two-mode networks. The reason for this is that a faster algorithm is needed for blockmodeling linked networks that can better scale to larger networks. Examples of linked networks include multilevel networks, dynamic networks, dynamic multilevel networks, and meta-networks. Generalized blockmodeling has been developed for linked/multilevel networks, yet the generalized blockmodeling approach is too slow for analyzing larger networks. Therefore, the flexibility of generalized blockmodeling is sacrificed for the speed of k-means-based approaches, thus allowing the analysis of larger networks. The presented algorithm is based on the two-mode k-means (or KL-means) algorithm for two-mode networks or matrices. As a side product, an algorithm for one-mode blockmodeling of one-mode networks is presented. The algorithm’s use on a dynamic multilevel network with more than 400 units is presented. A situation study is also conducted which shows that k-means based algorithms are superior to relocation algorithm-based methods for larger networks (e.g. larger than 800 units) and never much worse.     

Changing times: Migrants’ social network analysis and the challenges of longitudinal research

Focusing on migrant social networks, this paper draws upon the sociology of time to incorporate complex notions of temporality into the research process. In so doing, we consider firstly, the challenge of going ‘beyond the snapshot’ in data collection to capture dynamism through time. Secondly, we apply the concepts of timescapes to explore ways of addressing the wider context and the interplay between spatiality, temporality and relationality in migration research. We argue that integrating a mixed methods approach to SNA, crucially including visualisation, can provide a useful methodological and analytical framework to understand dynamics.SNA can also be helpful in bridging the personal and structural dimensions in migration research, by providing a meso level of analysis. However, it is also important to connect the investigation of local and transnational networks with an analysis of the broader social, economic and political contexts in which these take shape; in other words, connecting the micro and the meso with the wider macro level. Drawing upon reflections from our migration research studies, we argue that different combinations of quantitative, qualitative and visual methods do not just provide richer sets of data and insights, but can allow us to better connect conceptualisations – and ontologies – of social networks with specific methodological frameworks.     

A new look at clustering coefficients with generalization to weighted and multi-faction networks

In this paper we propose a new method for studying local and global clustering in networks employing random walk pairs. The method is intuitive and directly generalizes standard local and global clustering coefficients to weighted networks and networks containing nodes of multiple types. In the case of two-mode networks the values obtained for commonly considered social networks are in sharp contrast to those obtained, for instance, by the method of Opsahl (2013), and provide a different viewpoint for clustering. The approach is also applicable in questions related to the general study of segregation and homophily. Applications to existent data sets are considered.     

Logit Models for Affiliation Networks

Once confined to networks in which dyads could be reasonably assumed to be independent, the statistical analysis of network data has blossomed in recent years. New modeling and estimation strategies have made it possible to propose and evaluate very complex structures of dependency between and among ties in social networks. These advances have focused exclusively on one-mode networks—that is, networks of direct ties between actors. We generalize these models to affiliation networks, networks in which actors are tied to each other only indirectly through belonging to some group or event. We formulate models that allow us to study the (log) odds of an actor's belonging to an event (or an event including an actor) as a function of properties of the two-mode network of actors' memberships in events. We also provide illustrative analysis of some classic data sets on affiliation networks.     

Multitudinous identities: a qualitative and network analysis of the 15M collective identity

The emergence of network-movements since 2011 has opened the debate around the way in which social media and networked practices make possible innovative forms of collective identity. We briefly review the literature on social movements and ‘collective identity’, and show the tension between different positions stressing either organization or culture, the personal or the collective, aggregative or networking logics. We argue that the 15M (indignados) network-movement in Spain demands conceptual and methodological innovations. Its rapid emergence, endurance, diversity, multifaceted development and adaptive capacity, posit numerous theoretical and methodological challenges. We show how the use of structural and dynamic analysis of interaction networks (in combination with qualitative data) is a valuable tool to track the shape and change of what we term the ‘systemic dimension’ of collective identities in network-movements. In particular, we introduce a novel method for synchrony detection in Facebook activity to identify the distributed, yet integrated, coordinated activity behind collective identities. Applying this analytical strategy to the 15M movement, we show how it displays a specific form of systemic collective identity we call ‘multitudinous identity’, characterized by social transversality and internal heterogeneity, as well as a transient and distributed leadership driven by action initiatives. Our approach attends to the role of distributed interaction and transient leadership at a mesoscale level of organizational dynamics, which may contribute to contemporary discussions of collective identity in network-movements.     

Socio-material network analysis: A mixed method study of five European artistic collectives

In this paper, I argue that we can better understand the relationship between social structure and materiality by combining qualitative analysis of practices in shared physical space with statistical analysis. Drawing on the two-mode approach, I treat social and material structures together with the relationship between them as a two-level socio-material network. In a mixed method study, formalized ethnographic data on such networks in five European artistic collectives are subjected to multilevel exponential random graph modelling. It sheds light on how different kinds of interpersonal ties condition the engagement of individuals with similar materiality over time.     

Fast clustering for signed graphs based on random walk gap

Signed graphs are often used as models for social media mining, social networks analysis and nature language processing. In this paper, we study clustering algorithms for signed graphs that can be scaled for use in large-scale signed networks. A proposed mechanism, called a random walk gap (RWG), is used to extract more cluster structure information. RWG uses two types of random walks on signed graphs. The first considers positive edges only. The second takes negative edges into account. Three types of edges in signed graphs are identified and their different characteristics in terms of transition probability changes are determined for the two types of random walk graphs. Different characteristics contain different information about cluster structure and a RWG matrix is used to reflect the differences. The RWG matrix is used to adjust the weights of edges in signed graphs. This is the first study to perform a random walk on negative edges. A fast clustering for signed graphs (FCSG) algorithm is then proposed. This FCSG is compared with existing methods. The computational times for different algorithms are measured. The experiments show that the proposed FCSG algorithm gives better results than existing algorithms based on the performance criteria of imbalance and modularity.     

Dynamic network analysis of contact diaries

Analyzing two-mode networks linking actors to events they attend may help to uncover the structure and evolution of social networks. This classic social network insight is particularly valuable in the analysis of data extracted from contact diaries where contact events produce — and at the same time are the product of relations among participants. Contact events may comprise any number of actors meeting at a specific point in time. In this paper we recall the correspondence between two-mode actor–event networks and hypergraphs, and propose relational hyperevent models (RHEM) as a general modeling framework for networks of time-stamped multi-actor events in which the diarist (“ego”) simultaneously meets several of her alters. RHEM can estimate event intensities associated with each possible subset of actors that may jointly participate in events, and test network effects that may be of theoretical or empirical interest. Examples of such effects include preferential attachment, prior shared activity (familiarity), closure, and covariate effects explaining the propensity of actors to co-attend events. Statistical tests of these effects can uncover processes that govern the formation and evolution of informal groups among the diarist’s alters. We illustrate the empirical value of RHEM using data comprising almost 2000 meeting events of former British Prime Minister Margaret Thatcher with her cabinet ministers, transcribed from contact diaries covering her first term in office (1979–1983).     

Basic notions for the analysis of large two-mode networks

Many large real-world networks actually have a two-mode nature: their nodes may be separated into two classes, the links being between nodes of different classes only. Despite this, and despite the fact that many ad hoc tools have been designed for the study of special cases, very few exist to analyse (describe, extract relevant information) such networks in a systematic way. We propose here an extension of the most basic notions used nowadays to analyse large one-mode networks (the classical case) to the two-mode case. To achieve this, we introduce a set of simple statistics, which we discuss by comparing their values on a representative set of real-world networks and on their random versions. This makes it possible to evaluate their relevance in capturing properties of interest in two-mode networks.