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.     

A multiple indicator approach to blockmodeling signed networks

Regardless of whether the focus is on algebraic structures, elaborating role structures or the simple delineation of concrete social structures, generalized blockmodeling faces a pair of vulnerabilities. One is sensitivity to poor quality of the relational data and the other is a risk of over fitting blockmodels to the details of specific networks. Over fitting blockmodels can lead to multiple equally well fitting partitions where choices cannot be made between them on a principled basis. This paper presents a method of tackling these problems by viewing (when possible) observed social relations as multiple indicators of an underlying affect dimension. Quadratic assignment methods using matching coefficients, product moment correlations and Goodman and Kruskal's gamma are used to assess the appropriateness of using the sum of observed relations as input for applying generalized blockmodeling. Data for four groups are used to show the value of this approach within which multiple equally well fitting blockmodels for single relations are replaced by unique (or near-unique) partitions of the summed data. This strategy is located also within a broader problem of blockmodeling three-dimensional networks data and suggestions are made for future work.     

Generalized blockmodeling of valued networks

The paper presents several approaches to generalized blockmodeling of valued networks, where values of the ties are assumed to be measured on at least interval scale. The first approach is a straightforward generalization of the generalized blockmodeling of binary networks [Doreian, P., Batagelj, V., Ferligoj, A., 2005. Generalized Blockmodeling. Cambridge University Press, New York.] to valued blockmodeling. The second approach is homogeneity blockmodeling. The basic idea of homogeneity blockmodeling is that the inconsistency of an empirical block with its ideal block can be measured by within block variability of appropriate values. New ideal blocks appropriate for blockmodeling of valued networks are presented together with definitions of their block inconsistencies.     

A deviational approach to blockmodeling of valued networks

This article proposes a novel approach to blockmodeling of valued (one-mode) networks where the identification of (binary) block patterns in the valued relations differ from existing approaches. Rather than looking at the absolute values of relations, or examining valued ties on a per-actor basis (cf. Nordlund, 2007), the approach identifies prominent (binary) ties on the basis of deviations from expected values. By comparing the distribution of each actor's valued relations to its alters with the macro-level distributions of total in- and outdegrees, prominent (1) and non-prominent (0) ties are determined both on a per-actor-to-actor and a per-actor-from-actor basis. This allows for a direct interpretation of the underlying functional anatomy of a non-dichotomized valued network using the standard set of ideal blocks as found in generalized blockmodeling of binary networks.In addition to its applicability for direct blockmodeling, the article also suggests a novel indirect measure of deviational structural equivalence on the basis of such deviations from expected values.Exemplified with the note-sharing data in Žiberna (2007a), citations among social work journals (Baker, 1992), and total commodity trade among EU/EFTA countries as of 2010, both the direct and indirect approach produce results that are more sensitive to variations at the dyadic level than existing approaches. This is particularly evident in the case of the EU/EFTA trade network, where the indirect approach yields partitions and blockmodels in support of theories of regional trade, despite the significantly skewed valued degree distribution of the dataset.     

Direct blockmodeling of valued and binary networks: a dichotomization-free approach

A long-standing open problem with direct blockmodeling is that it is explicitly intended for binary, not valued, networks. The underlying dilemma is how empirical valued blocks can be compared with ideal binary blocks, an intrinsic problem in the direct approach where partitions are solely determined through such comparisons. Addressing this dilemma, valued networks have either been dichotomized into binary versions, or novel types of ideal valued blocks have been introduced. Both these workarounds are problematic in terms of interpretability, unwanted data reduction, and the often arbitrary setting of model parameters.This paper proposes a direct blockmodeling approach that effectively bypasses the dilemma with blockmodeling of valued networks. By introducing an adaptive weighted correlation-based criteria function, the proposed approach is directly applicable to both binary and valued networks, without any form of dichotomization or transformation of the valued (or binary) data at any point in the analysis, while still using the conventional set of ideal binary blocks from structural, regular and generalized blockmodeling.The proposed approach seemingly solves two other open problems with direct blockmodeling. First, its standardized goodness-of-fit measure allows for direct comparisons across solutions, within and between networks of different sizes, value types, and notions of equivalence. Secondly, through an inherent bias of point-biserial correlations, the approach puts a premium on solutions that are closer to the mid-point density of blockmodels. This, it is argued, translates into solutions that are more intuitive and easier to interpret.The approach is demonstrated by structural, regular and generalized blockmodeling applications of six classical binary and valued networks. Finding feasible and intuitive optimal solutions in both the binary and valued examples, the approach is proposed not only as a practical, dichotomization-free heuristic for blockmodeling of valued networks but also, through its additional benefits, as an alternative to the conventional direct approach to blockmodeling.     

Actor non-response in valued social networks: The impact of different non-response treatments on the stability of blockmodels

Social network data usually contain different types of errors. One of them is missing data due to actor non-response. This can seriously jeopardize the results of analyses if not appropriately treated. The impact of missing data may be more severe in valued networks where not only the presence of a tie is recorded, but also its magnitude or strength. Blockmodeling is a technique for delineating network structure. We focus on an indirect approach suitable for valued networks. Little is known about the sensitivity of valued networks to different types of measurement errors. As it is reasonable to expect that blockmodeling, with its positional outcomes, could be vulnerable to the presence of non-respondents, such errors require treatment. We examine the impacts of seven actor non-response treatments on the positions obtained when indirect blockmodeling is used. The start point for our simulation are networks whose structure is known. Three structures were considered: cohesive subgroups, core-periphery, and hierarchy. The results show that the number of non-respondents, the type of underlying blockmodel structure, and the employed treatment all have an impact on the determined partitions of actors in complex ways. Recommendations for best practices are provided.     

Notes on blockmodeling

We attempt to develop further the blockmodeling of networks, so as better to capture the network structure. For this purpose a richer structure than ordinary (valued) graphs has to be used for a model. Such structures are valued graphs with typified (complete, dominant, regular, etc.) connections. Based on the proposed formalization, the blockmodeling is cast as an optimization problem.     

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.     

Graph and semigroup homomorphisms on networks of relations

The algebraic definitions presented here are motivated by our search for an adequate formalization of the concepts of social roles as regularities in social network patterns. The theorems represent significant homomorphic reductions of social networks which are possible using these definitions to capture the role structure of a network. The concepts build directly on the pioneering work of S.F. Nadel (1957) and the pathbreaking approach to blockmodeling introduced by Lorrain and White (1971) and refined in subsequent years (White, Boorman and Breiger 1976;Boorman and White 1976; Arabie, Boorman and Levitt, 1978; Sailer, 1978).Blockmodeling is one of the predominant techniques for deriving structural models of social networks. When a network is represented by a directed multigraph, a blockmodel of the multigraph can be characterized as mapping points and edges onto their images in a reduced multigraph. The relations in a network or multigraph can also be composed to form a semigroup.In the first part of the paper we examine “graph” homomorphisms, or homomorphic mappings of the points or actors in a network. A family of basic concepts of role equivalence are introduced, and theorems presented to show the structure preserving properties of their various induced homomorphisms. This extends the “classic” approach to blockmodeling via the equivalence of positions.Lorrain and White (1971), Pattison (1980), Boyd, 1980, Boyd, 1982, and most recently Bonacich (1982) have explored the topic taken up in the second part of this paper, namely the homomorphic reduction of the semigroup of relations on a network, and the relation between semigroup and graph homomorphisms. Our approach allows us a significant beginning in reducing the complexity of a multigraph by collapsing relations which play a similar “role” in the network.     

Networks containing negative ties

Social network analysts have often collected data on negative relations such as dislike, avoidance, and conflict. Most often, the ties are analyzed in such a way that the fact that they are negative is of no consequence. For example, they have often been used in blockmodeling analyses where many different kinds of ties are used together and all ties are treated the same, regardless of meaning. However, sometimes we may wish to apply other network analysis concepts, such as centrality or cohesive subgroups. The question arises whether all extant techniques are applicable to negative tie data. In this paper, we consider in a systematic way which standard techniques are applicable to negative ties and what changes in interpretation have to be made because of the nature of the ties. We also introduce some new techniques specifically designed for negative ties. Finally we show how one of these techniques for centrality can be extended to networks with both positive and negative ties to give a new centrality measure (PN centrality) that is applicable to directed valued data with both positive and negative ties.     

Cluster analysis of multiplex networks: Defining composite network measures

Social relations are multiplex by nature: actors in a group are tied together by various types of relationships. To understand and explain group processes it is, therefore, important to study multiple social networks simultaneously in a given group. However, with multiplexity the complexity of data also increases. Although some multivariate network methods (e.g. Exponential Random Graph Models, Stochastic Actor-oriented Models) allow to jointly analyze multiple networks, modeling becomes complicated when it focuses on more than a few (2–4) network dimensions. In such cases, dimension reduction methods are called for to obtain a manageable set of variables. Drawing on existing statistical methods and measures, we propose a procedure to reduce the dimensions of multiplex network data measured in multiple groups. We achieve this by clustering the networks using their pairwise similarities, and constructing composite network measures as combinations of the networks in each resulting cluster. The procedure is demonstrated on a dataset of 21 interpersonal network dimensions in 18 Hungarian high-school classrooms. The results indicate that the network items organize into three well-interpretable clusters: positive, negative, and social role attributions. We show that the composite networks defined on these three relationship groups overlap but do not fully coincide with the network measures most often used in adolescent research, such as friendship and dislike.     

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.     

Uncovering CSR meaning networks: A cross-national comparison of Turkey and Slovenia

This study addressed an important question about the meaning of corporate social responsibility (CSR), and how it is measured. Based on a comparison of the meaning networks of CSR in two countries with fundamentally different cultural and socioeconomic backgrounds, we argue that there is a need for an institutional perspective when studying CSR associations and expectations in a particular society. Thus empirical study involved the use of three methods the word-association technique, social network analysis, and blockmodeling using Pajek software; to provide deep insight into the structure of CSR associations. The findings suggest that the two societies have diverse collective cognitive structures regarding CSR. In Turkey, the philanthropic understanding of CSR is highly dominant, while the Slovenian social meaning of CSR is multidimensional. The findings point to the social construction of the concept of CSR with implications both for academic research and practice.     

Exploring the joint dynamics of intercity internet and corporate networks: a stochastic actor‐based modelling approach

In this article, I show one possible solution to synthesis dynamics in multiple intercity networks. I adopt a stochastic actor‐based modelling approach to explore the co‐evolution of an intercity corporate network of 57 globalized advanced producer service firms across 93 cities, and another intercity internet network between these 93 cities, for the period 2004–2010. Stochastic actor‐based models (SABMs) help to connect interactions among cities and firms on the local scale with empirically observed networks on the global scale. My analysis accounts for the co‐evolution/interdependence among multiple world city networks (WCNs) and associated network changes in individual WCNs with exogenous city‐related covariates and endogenous local network structures.     

Modeling the dynamism of HIV information diffusion in multiplex networks of homeless youth

Cascade and threshold models are widely used to predict information diffusion in social networks, yet their characterization of networks as static and monoplex limit their ability to accurately predict how information propagates in dynamic, multiplex social environments. Using data from a peer-led HIV prevention intervention for homeless youth, we determine whether manipulating the baseline social network by (1) adding ties observed at later time points, and (2) accounting for alternative relational contexts improves each model’s predictive accuracy. Results show that the addition of new ties improves the performance of both models, while substituting the context of interaction yields only minor improvements.     

Exploring the stability of communication network metrics in a dynamic nursing context

Network stability is of increasing interest to researchers as they try to understand the dynamic processes by which social networks form and evolve. Because hospital patient care units (PCUs) need flexibility to adapt to environmental changes (Vardaman et al., 2012), their networks are unlikely to be uniformly stable and will evolve over time. This study aimed to identify a metric (or set of metrics) sufficiently stable to apply to PCU staff information sharing and advice seeking communication networks over time. Using Coefficient of Variation, we assessed both Across Time Stability (ATS) and Global Stability over four data collection times (Baseline and 1, 4, and 7 months later). When metrics were stable using both methods, we considered them “super stable.” Nine metrics met that criterion (Node Set Size, Average Distance, Clustering Coefficient, Density, Weighted Density, Diffusion, Total Degree Centrality, Betweenness Centrality, and Eigenvector Centrality). Unstable metrics included Hierarchy, Fragmentation, Isolate Count, and Clique Count. We also examined the effect of staff members’ confidence in the information obtained from other staff members. When confidence was high, the “super stable” metrics remained “super stable,” but when low, none of the “super stable” metrics persisted as “super stable.” Our results suggest that nursing units represent what Barker (1968) termed dynamic behavior settings in which, as is typical, multiple nursing staff must constantly adjust to various circumstances, primarily through communication (e.g., discussing patient care or requesting advice on providing patient care), to preserve the functional integrity (i.e., ability to meet patient care goals) of the units, thus producing the observed stability over time of nine network metrics. The observed metric stability provides support for using network analysis to study communication patterns in dynamic behavior settings such as PCUs.     

Effects of missing data in social networks

We perform sensitivity analyses to assess the impact of missing data on the structural properties of social networks. The social network is conceived of as being generated by a bipartite graph, in which actors are linked together via multiple interaction contexts or affiliations. We discuss three principal missing data mechanisms: network boundary specification (non-inclusion of actors or affiliations), survey non-response, and censoring by vertex degree (fixed choice design), examining their impact on the scientific collaboration network from the Los Alamos E-print Archive as well as random bipartite graphs. The simulation results show that network boundary specification and fixed choice designs can dramatically alter estimates of network-level statistics. The observed clustering and assortativity coefficients are overestimated via omission of affiliations or fixed choice thereof, and underestimated via actor non-response, which results in inflated measurement error. We also find that social networks with multiple interaction contexts may have certain interesting properties due to the presence of overlapping cliques. In particular, assortativity by degree does not necessarily improve network robustness to random omission of nodes as predicted by current theory.     

Partitioning large signed two-mode networks: Problems and prospects

While a substantial amount of attention within social network analysis (SNA) has been given to the study of one-mode networks, there is an increasing consideration of two-mode networks. Recent research on signed networks resulted in the relaxed structural balance (RSB) approach and its subsequent extension to signed two-mode networks involving social actors and social objects. We extend this approach to large signed two-mode networks, and address the methodological issues that arise. We develop tools to partition these types of networks and compare them with other approaches using a recently collected dataset of United Nations General Assembly roll call votes. Although our primary purpose is methodological, we take the first step towards bridging Heider's structural balance theory with recent theorizing in international relations on soft balancing of power processes.     

The Analysis of Duocentric Social Networks: A Primer

Marriages and other intimate partnerships are facilitated or constrained by the social networks within which they are embedded. To date, methods used to assess the social networks of couples have been limited to global ratings of social network characteristics or network data collected from each partner separately. In the current article, the authors offer new tools for expanding on the existing literature by describing methods of collecting and analyzing duocentric social networks, that is, the combined social networks of couples. They provide an overview of the key considerations for measuring duocentric networks, such as how and why to combine separate network interviews with partners into one shared duocentric network, the number of network members to assess, and the implications of different network operationalizations. They illustrate these considerations with analyses of social network data collected from 57 low‐income married couples, presenting visualizations and quantitative measures of network composition and structure.     

Unpacking Burt’s constraint measure

Burt (1992) proposed two principal measures of structural holes, effective size and constraint. However, the formulas describing the measures are somewhat opaque and have led to a certain amount of confusion. Borgatti (1997) showed that, for binary data, the effective size formula could be written very simply as degree (ego network size) minus average degree of alters within the ego network. The present paper presents an analogous reformulation of the constraint measure. We also derive minima and maxima for constraint, showing that, for small ego networks, constraint can be larger than one, and for larger ego networks, constraint cannot get as large as one. We also show that for networks with more than seven alters, the maximum constraint does not occur in a maximally dense or closed network, but rather in a relatively sparse “shadow ego network”, which is a network that contains an alter (the shadow ego) that is connected to every other alter, and where no other alter-alter ties exist.