A new method for finding hierarchical subgroups from networks

We present a new method for decomposing a social network into an optimal number of hierarchical subgroups. With a perfect hierarchical subgroup defined as one in which every member is automorphically equivalent to each other, the method uses the REGGE algorithm to measure the similarities among nodes and applies the k-means method to group the nodes that have congruent profiles of dissimilarities with other nodes into various numbers of hierarchical subgroups. The best number of subgroups is determined by minimizing the intra-cluster variance of dissimilarity subject to the constraint that the improvement in going to more subgroups is better than a network whose n nodes are maximally dispersed in the n-dimensional space would achieve. We also describe a decomposability metric that assesses the deviation of a real network from the ideal one that contains only perfect hierarchical subgroups. Four well known network data sets are used to demonstrate the method and metric. These demonstrations indicate the utility of our approach and suggest how it can be used in a complementary way to Generalized Blockmodeling for hierarchical decomposition.     

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.     

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.     

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

Discerning the essential structure of social networks is a major task. Yet, social network data usually contain different types of errors, including missing data that can wreak havoc during data analyses. Blockmodeling is one technique for delineating network structure. While we know little about its vulnerability to missing data problems, it is reasonable to expect that it is vulnerable given its positional nature. We focus on actor non-response and treatments for this. We examine their impacts on blockmodeling results using simulated and real networks. A set of ‘known’ networks are used, errors due to actor non-response are introduced and are then treated in different ways. Blockmodels are fitted to these treated networks and compared to those for the known networks. The outcome indicators are the correspondence of both position memberships and identified blockmodel structures. Both the amount and type of non-response, and considered treatments, have an impact on delineated blockmodel structures.     

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.     

A new criterion function for exploratory blockmodeling for structural and regular equivalence

We present a new criterion function for blockmodeling two-way two-mode relation matrices when the number of blocks as well as the equivalence relation are unknown. For this, we specify a measure of fit based on data compression theory, which allows for the comparison of blockmodels of different sizes and block types from different equivalence relations. We arm an alternating optimization algorithm with this criterion and demonstrate that the method reproduces consensual blockings of three datasets without any pre-specification. We perform a simulation study where we compare our compression-based criterion to the commonly used criterion that measures the number of inconsistencies with an ideal blockmodel.     

A generalized model of relational similarity

This paper introduces two principles for relational similarity, and based on these principles it proposes a novel geometric representation for similarity. The first principle generalizes earlier measures of similarity such as Pearson-correlation and structural equivalence: while correlation and structural equivalence measure similarity by the extent to which the actors have similar relationships to other actors or objects, the proposed model views two actors similar if they have similar relationships to similar actors or objects. The second principle emphasizes consistency among similarities: not only are actors similar if they have similar relationships to similar objects, but at the same time objects are similar if similar actors relate to them similarly. We examine the behavior of the proposed similarity model through simulations, and re-analyze two classic datasets: the Davis et al. (1941) data on club membership and the roll-call data of the U.S. Senate. We find that the generalized model of similarity is especially useful if (1) the dimensions of comparison are not independent, or (2) the data are sparse, or (3) the boundaries between clusters are not clear.     

An algorithm and metric for network decomposition from similarity matrices: Application to positional analysis

We present an algorithm for decomposing a social network into an optimal number of structurally equivalent classes. The k-means method is used to determine the best decomposition of the social network for various numbers of subgroups. The best number of subgroups into which to decompose a network is determined by minimizing the intra-cluster variance of similarity subject to the constraint that the improvement in going to more subgroups is better than a random network would achieve. We also describe a decomposability metric that assesses how closely the derived decomposition approaches an ideal network having only structurally equivalent classes.