Dense core model for cohesive subgraph discovery

Discovery of cohesive subgraphs is an important issue in social network analysis. As representative cohesive subgraphs, pseudo cliques have been developed by relaxing the perfection of cliques. By enumerating pseudo clique subgraphs, we can find some structures of interest such as a star-like structure. However, a little more complicated structures such as a core/periphery structure is still hard to be found by them. Therefore, we propose a novel pseudo clique called ρ-dense core and show the connection with the other pseudo cliques. Moreover, we show that a set of ρ-dense core subgraphs gives an optimal solution in a graph partitioning problem. Several experiments on real-life networks demonstrated the effectiveness for cohesive subgraph discovery.     

Goal specific social capital and job satisfaction: Effects of different types of networks on instrumental and social aspects of work

This paper addresses the question “To what extent can job satisfaction be explained as the revenue of social capital?” By conceiving someone’s social network as social capital we specify conditions under which social ties do lead to job satisfaction. We inquire into the idea of goal specificity of social capital, which implies that a network with a given structure and content will have different impacts on various aspects of job satisfaction. If the content of the ties and the structure of the network at the job engender material well-being or produce social approval, satisfaction with the corresponding job aspects increases. Data were collected in 1993 using written questionnaires in two Dutch governmental agencies, one with 32 and the other with 44 employees. These workers’ networks were charted using nine name-generating questions.Social capital, it turns out, is not an all-purpose good but one that is goal specific, even within a single domain of life such as work. Three effects stand out: First, the structure of the network and the content of the ties do matter. Networks of strategic, work-related ties promote an employee’s satisfaction with instrumental aspects of the job, like income, security, and career opportunities. Second, closed networks of identity-based solidarity ties improve an employee’s satisfaction with social aspects of the job, like the general social climate at work and cooperation with management and colleagues. Third, a network with a bow–tie structure (i.e., where a focal actor is the link between two or more mutually exclusive cliques) generally has strong negative effects on satisfaction with the social side of the job; although a bow–tie type network of trusting ties does increase satisfaction with the social side. This implies that Krackhardt’s hypothesis on the unpleasant feelings produced by bow–tie type networks has to be specified for the content of the ties that constitute such a network. The most important conclusion of our analysis is that goal specificity of social capital has implications for both structure and content of social networks. Achievement of a particular goal, such as satisfaction at work, requires not only networks of a certain structure or ties with a particular content, but specifically structured networks of ties with a particular content.     

Statistical power of the social network autocorrelation model

The network autocorrelation model has become an increasingly popular tool for conducting social network analysis. More and more researchers, however, have documented evidence of a systematic negative bias in the estimation of the network effect (ρ). In this paper, we take a different approach to the problem by investigating conditions under which, despite the underestimation bias, a network effect can still be detected by the network autocorrelation model. Using simulations, we find that moderately-sized network effects (e.g., ρ = .3) are still often detectable in modest-sized networks (i.e., 40 or more nodes). Analyses reveal that statistical power is primarily a nonlinear function of network effect size (ρ) and network size (N), although both of these factors can interact with network density and network structure to impair power under certain rare conditions. We conclude by discussing implications of these findings and guidelines for users of the autocorrelation model.     

Computing continuous core/periphery structures for social relations data with MINRES/SVD

When diagonal values are missing or excluded, MINRES is a natural continuous model for the core/periphery structure of a symmetric social network matrix. Symmetric models, however, are not so useful when dealing with asymmetric data. Singular value decomposition (SVD) is a natural choice to model asymmetry, but this method also requires the presence of diagonal values. In this paper we offer an alternative, more general, approach to continuous core/periphery structures, the minimum residual singular value decomposition (MINRES/SVD), where each node in the network receives two indices, an “in-coreness” and an “out-coreness.” The algorithm for computing these coreness vectors is a least squares computation similar to, but distinct from the SVD, again because of the missing diagonal values. And in contrast to the standard, symmetric MINRES algorithm, we can more accurately model asymmetric matrices. This allows us to distinguish, for example, countries in the world economy that are more in the exporting core than they are in the importing core. We propose two nested PRE (proportional reduction of error) measures of fit: (1) the PRE from the MINRES vector with respect to the data and (2) the PRE of the product of the two MINRES/SVD vectors. Applying the resulting method to citations between journals and to international trade in clothing, we illustrate insights gained from being able to model asymmetrical flow patterns. Finally, two permutation tests are introduced to test independently for the MINRES and MINRES/SVD results.     

Random sampling of alters from networks: A promising direction in egocentric network research

The social network perspective has great potential for advancing knowledge of social mechanisms in many fields. However, collecting egocentric (i.e., personal) network data is costly and places a heavy burden on respondents. This is especially true of the task used to elicit information on ties between network members (i.e., alter-alter ties or density matrix), which grows exponentially in length as network size increases. While most existing national surveys circumvent this problem by capping the number of network members that can be named, this strategy has major limitations. Here, we apply random sampling of network members to reduce cost, respondent burden, and error in network studies. We examine the effectiveness and reliability of random sampling in simulated and real-world egocentric network data. We find that in estimating sample/population means of network measures, randomly selecting a small number of network members produces only minor errors, regardless of true network size. For studies that use network measures in regressions, randomly selecting the mean number of network members (e.g., randomly selecting 10 alters when mean network size is 10) is enough to recover estimates of network measures that correlate close to 1 with those of the full sample. We conclude with recommendations for best practices that will make this versatile but resource intensive methodology accessible to a wider group of researchers without sacrificing data quality.     

Validation of tie corroboration and reported alter characteristics among a sample of young men who have sex with men

The differences between direct ties (i.e., ties between a respondent and their nominees) and ties between nominees (indirect) are key to understanding network structure, yet remain understudied. Within a sample of 175 young men who have sex with men, we explored the corroboration of sex and drug ties, and factors associated with corroboration. The majority of instances in which there was no corroboration for either sex or drug ties was due to one individual not appearing in another respondent’s network. When an individual did appear in another respondent’s network, direct sex and drug ties were corroborated in most cases. We also found that more indirect sex ties were corroborated than direct sex ties (95.7% vs. 88.9%), but the reverse was true for indirect versus direct drug ties (73.1% vs. 84.1%). Strength of relationship and frequency of communication were both associated with confirmed direct ties, but not with indirect ties. Based on these findings, we recommend that direct and indirect ties be treated differently in network analyses.     

An exact algorithm for a core/periphery bipartitioning problem

The discrete optimization problem associated with partitioning a set of actors into core and periphery subsets has typically been approached using approximate procedures such as exchange heuristics, genetic algorithms, and simulated annealing. Although these procedures are effective and scalable for large networks, they do not guarantee an optimal bipartition. In this paper, an exact algorithm is presented for a core/periphery bipartitioning problem. Unlike the approximate procedures in the extant literature, this new algorithm, which is based on the principles of branch-and-bound programming, affords a guarantee of an optimal bipartition. Computational results for empirical and simulated data sets reveal that the proposed algorithm is extremely efficient for networks with 40 or fewer actors, and is often scalable for networks with up to 60 actors.     

The distant core: social solidarity,social distance and interpersonal ties in core–periphery structures

We examine three hypotheses at the foundation of theories concerned with the organization of social space and social solidarity in differentiated groups. The most important of these hypotheses is that interpersonal ties between actors in different positions of a social structure foster social solidarity; however, the theories are silent on the question of whether this effect of interpersonal ties is maintained regardless of the distance that separates the positions of two actors in the group’s social space. In addition, the current zeitgeist on the organization of social space hypothesizes that interpersonal solidarity and ties are negatively associated with the distance that separates the positions of actors in social space. Although interpersonal ties foster solidarity, social distance reduces the likelihood of interpersonal ties and solidarity. Our evidence suggests unqualified support only for the first hypothesis. Surprisingly, the expected negative effects of social distance on interpersonal ties and solidarity appear to be properties of particular forms of social organization and are not ubiquitous implications of social differentiation. These negative effects are more or less pronounced (even reversible) in core–periphery structures depending upon the distance between the core and peripheral positions in the social space of the group.     

Introduction to stochastic actor-based models for network dynamics

Stochastic actor-based models are models for network dynamics that can represent a wide variety of influences on network change, and allow to estimate parameters expressing such influences, and test corresponding hypotheses. The nodes in the network represent social actors, and the collection of ties represents a social relation. The assumptions posit that the network evolves as a stochastic process ‘driven by the actors’, i.e., the model lends itself especially for representing theories about how actors change their outgoing ties. The probabilities of tie changes are in part endogenously determined, i.e., as a function of the current network structure itself, and in part exogenously, as a function of characteristics of the nodes (‘actor covariates’) and of characteristics of pairs of nodes (‘dyadic covariates’). In an extended form, stochastic actor-based models can be used to analyze longitudinal data on social networks jointly with changing attributes of the actors: dynamics of networks and behavior.     

On the core of characteristic function games associated with exchange networks

An exchange network is a social system in which the actors gain valued resources from bilateral transactions, but an opportunity to negotiate a deal is given only to those pairs of actors whose positions are tied with each other in a fixed communication network. A transaction consists in a mutually agreed-on division of a resource pool assigned to a network line. An additional constraint imposed on such a network restricts the range of transaction sets which may happen in a single negotiation round to those consistent with a given “exchange regime.” Under the one-exchange regime every actor is permitted to make no more than one deal per round. Bienenstock and Bonacich [Bienenstock, E.J., Bonacich, P., 1992. The core as a solution to exclusionary networks. Social Networks 14, 231–243] proposed to represent a one-exchange network with an n-person game in characteristic function form. The aim of this paper is to develop a mathematical theory of games associated with homogenous one-exchange networks (network homogeneity means that all lines are assigned resource pools of the same size). The focus is on the core, the type of solution considered most important in game theory. In particular, all earlier results obtained by Bonacich are re-examined and there is given a new graph-theoretic necessary and sufficient condition for the existence of nonempty core for the game representing a homogenous one-exchange network.     

Spectral goodness of fit for network models

We introduce a new statistic, ‘spectral goodness of fit’ (SGOF) to measure how well a network model explains the structure of the pattern of ties in an observed network. SGOF provides a measure of fit analogous to the standard R² in linear regression. Additionally, as it takes advantage of the properties of the spectrum of the graph Laplacian, it is suitable for comparing network models of diverse functional forms, including both fitted statistical models and algorithmic generative models of networks. After introducing, defining, and providing guidance for interpreting SGOF, we illustrate the properties of the statistic with a number of examples and comparisons to existing techniques. We show that such a spectral approach to assessing model fit fills gaps left by earlier methods and can be widely applied.     

More or less guanxi: Trust is 60% network context, 10% individual difference

The strong ties known in China as guanxi can be distinguished by a high level of trust relatively independent of the surrounding social structure. Using network data from a stratified probability sample of 700 entrepreneurs citing 4664 contacts, we study guanxi relative to other relations to learn how much individual differences such as well-being, business differences, political participation and demographic factors matter for the guanxi distinction. Two findings stand out: First, the connection between trust and social network is robust to most differences between individuals, especially business and political differences. Trust variance is 60% network context, and 10% individual differences. Trust increases within a relationship as network closure increases around the relationship, but some relationships mature into guanxi ties within which trust is high and relatively independent of the surrounding social structure. Second, when individual differences matter, they concern social isolation. Guanxi ties are more distinct in the networks around entrepreneurs with small, marginal families, and around those with small, closed networks. Both categories of entrepreneurs are likely to experience difficulties with respect to resource access and doing business with people beyond their network, which may explain why longstanding guanxi ties linked to important events are particularly distinct for these entrepreneurs.     

Duocentered networks

When a pair of individuals is central to a research problem (e.g., husband and wife, PhD student and supervisor) the concept of “duocentered” networks can be defined as a useful extension of egocentered networks. This new structure consists of a pair of central egos and their direct links with alters, instead of just one central ego as in the egocentered networks or multiple egos as in complete networks. The key point in this kind of network is that ties exist between the central pair of egos and between them and all alters, but the ties among alters are not considered. Duocentered networks can also be considered as a compromise between egocentered and complete networks. Complete network measurements are often costly to obtain and tend to contain a large proportion of missing data (especially for peripheral actors). Egocentered network data are less costly but a lot of information is lost with their use when a pair of individuals is the relevant unit of analysis.     

Whom do we lose? The case of dissimilarity in personal networks

Previous research finds that individuals tend to form ties with similar others much more often than with dissimilar others. However, we know relatively little about tie loss and to what extent this is driven by (dis)similarity. In this paper, we argue that ties to persons who are dissimilar with regard to gender, age, ethnicity, and education are lost faster than ties to similar persons – and we test three explanations for this faster decay of ties with dissimilar others: lack of meeting opportunities, preferences for similarity, and lower network embeddedness. To test these explanations, we analysed two waves of the Survey on the Social Networks of the Dutch (SSND, 2007, 2014). These SSND-waves contain comprehensive longitudinal panel data on ego networks of 441 respondents, who were interviewed about a wide range of relationships, their alters’ sociodemographic characteristics, where and when they met their alters, as well as how and whether they maintain these relationships. We modelled tie loss by event history analyses. Results show that ties to persons who were dissimilar are more likely to be lost faster, and that tie loss occurs mostly in the early years of a relationship. However, meeting opportunities, preferences for similarity, and network embeddedness are unable to explain why ties to dissimilar others are lost faster. We conclude that dissimilarity is a powerful driver of tie loss, and that more arguments and research are needed to fully understand the underlying mechanisms.     

Measuring ‘neighborhood’: Constructing network neighborhoods

This study attempts to measure neighborhood boundaries in a novel way by creating network neighborhoods based on the density of social ties among adolescents. We create valued matrices based on social ties and physical distance between adolescents in the county. We then perform factor analyses on these valued matrices to detect these network neighborhoods. The resulting network neighborhoods show considerable spatial contiguity. We assess the quality of these aggregations by comparing the degree of agreement among residents assigned to the same network neighborhood when assessing various characteristics of their “neighborhood”, along with traditional definitions of neighborhoods from Census aggregations. Our findings suggest that these network neighborhoods are a valuable approach for “neighborhood” aggregation.     

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.     

Social network structure and the trade-off between social utility and economic performance

We put forward a computational multi-agent model capturing the impact of social network structure on individuals’ social trust, willingness to cooperate, social utility and economic performance. Social network structure is modeled as four distinct social capital dimensions: degree, centrality, bridging and bonding social capital. Model setup draws from socio-economic theory and empirical findings based on our novel survey dataset. Results include aggregate-level comparative statics and individual-level correlations. We find, inter alia, that societies that either are better connected, exhibit a lower frequency of local cliques, or have a smaller share of family-based cliques, record relatively better aggregate economic performance. As long as family ties are sufficiently valuable, there is a trade-off between aggregate social utility and economic performance, and small world networks are then socially optimal. We also find that in dense networks and trustful societies, there is a trade-off between individual social utility and economic performance; otherwise both outcomes are positively correlated in the cross section.     

How stable is the core discussion network?

Researchers have paid increasing attention to the core discussion network, the set of people we turn to when discussing important matters. Because the core discussion network is theorized to be composed of people's closest ties, not fleeting acquaintances, it is expected to be largely stable, evolving slowly over the span of people's lives. However, recent studies have shown that networks are strongly affected by the contexts in which people interact with others, and as people experience life course transitions, they also often enter new contexts – school, college, work, marriage, and retirement. We ask whether, as actors enter new social contexts, the core discussion network remains stable or changes rapidly. Based on original, longitudinal, qualitative and quantitative data on the experience of first-year graduate students in three academic departments in a large university, we examine the stability of the core discussion network over the first 6 and 12 months in this new context. We test four competing hypotheses that focus on strength of ties, new opportunities, obligations, and routine activity and predict, respectively, stasis, expansion, shedding, and substitution. We find that the core discussion network changes remarkably quickly, with little or no lag, and that it appears to do so because both the obligations that people face and the routine activities they engage in are transformed by new institutional environments. Findings suggest that core discussion network may be less a “core” network than a highly contextual support network in which people are added and dropped as actors shift from environment to environment.