The emergence of groups in the evolution of friendship networks

Friendship networks usually show a certain degree of segmentation: subgroups of friends. The explanation of the emergence of such groups from initially dyadic pair friendships is a difficult but important problem. In this paper we attempt to provide a first contribution to the explanation of subgroup formation in friendship networks by using the LS set as a definition for a friendship group. We construct a dynamic individual oriented model of friendship formation and provide preliminary simulation results that give an idea of how to continue the process of explaining group formation.     

Assessing and accounting for time heterogeneity in stochastic actor oriented models

This paper explores time heterogeneity in stochastic actor oriented models (SAOM) proposed by Snijders (Sociological Methodology. Blackwell, Boston, pp 361-395, 2001) which are meant to study the evolution of networks. SAOMs model social networks as directed graphs with nodes representing people, organizations, etc., and dichotomous relations representing underlying relationships of friendship, advice, etc. We illustrate several reasons why heterogeneity should be statistically tested and provide a fast, convenient method for assessment and model correction. SAOMs provide a flexible framework for network dynamics which allow a researcher to test selection, influence, behavioral, and structural properties in network data over time. We show how the forward-selecting, score type test proposed by Schweinberger (Chapter 4: Statistical modeling of network panel data: goodness of fit. PhD thesis, University of Groningen 2007) can be employed to quickly assess heterogeneity at almost no additional computational cost. One step estimates are used to assess the magnitude of the heterogeneity. Simulation studies are conducted to support the validity of this approach. The ASSIST dataset (Campbell et al. Lancet 371(9624):1595-1602, 2008) is reanalyzed with the score type test, one step estimators, and a full estimation for illustration. These tools are implemented in the RSiena package, and a brief walkthrough is provided.     

Identity-based learning and segregation in social networks under different institutional environments

To study the evolution of segregation in social networks across systems embedded in different institutional environments, we develop an identity-based learning model where segregation is stochastically conditioned by the initial distribution of the actor’s attention to identity and the updating of this distribution over time. The updating process, which we call the process of mutual learning multiplier, is based on an actor’s success and failure experiences in tying with the same-subgroup and cross-subgroup actors. Results from a Monte Carlo simulation of the model show that the mutual learning multiplier produces disproportional relationships between the initial distribution of identity attention and the level of segregation in social networks. We also find that those relationships are affected by the actors’ attention to structural holes, rate of learning from experience, system size, and the identity heterogeneity of the system. Overall, the model provides insights into various dynamics of network structuration across time and space.     

Friendship Networks Through Time: An Actor-Oriented Dynamic Statistical Network Model

We propose a class of actor-oriented statistical models for closed social networks in general, and friendship networks in particular. The models are random utility models developed within a rational choice framework. Based on social psychological and sociological theories about friendship, mathematical functions capturing expected utility of individual actors with respect to friendship are constructed. Expected utility also contains a random (unexplained) component. We assume that, given their restrictions and contact opportunities, individuals evaluate their utility functions and behave such that they maximize the expected amount of utility. The behavior under consideration is the expression of like and dislike (choice of friends). Theoretical mechanisms that are modelled are, e.g., the principle of diminishing returns, the tendency towards reciprocated choices, and the preference for friendship relations with similar others. Constraints imposed on individuals are, e.g., the structure of the existing network, and the distribution of personal characteristics over the respondents. The models are illustrated by means of a data-set collected among university freshmen at 7 points in time during 1994 and 1995.     

Unanimous opinions in social influence networks

In this paper, I show that persons reach unanimous opinions even when they have different initial opinions and different social influences in social influence networks. Friedkin and Johnsen introduced a model of social influence networks, and identified conditions for initially diverse opinions to converge. However, they did not examine conditions of “unanimous” convergence. Hence, I provide sufficient conditions of such unanimous consensus by focusing on three typical but conflicting social influences: the equal influence, the influence of the lowest opinion, and no influence. I show that unanimous opinions occur even when persons have antagonistic social influences such as the equal influence and the influence of the lowest opinion. I also demonstrate that the most cooperative type is the equal influence, but the most central type is the no influence.     

Structures induced by collections of subsets: a hypergraph approach

During recent years, much attention has been paid by anthropologists and sociologists to the analysis of social networks. These networks arise from dyadic relationships such as kinship or friendship and they have been studied using techniques derived from graph theory. Although the study of such networks can cast much light on the social structure of a population, many important aspects of this structure cannot be addressed using dyadic relationships alone. For example, group membership gives rise to natural non-dyadic relationships which will be distorted if they are forced into a dyadic mold. The purpose of this paper is to propose an analytical scheme which will permit the study of structure induced by non-dyadic relationships. The concepts used derive from the theory of hypergraphs, and it is shown that these concepts permit a wide variety of structural questions to be posed.     

A multilevel network study of the effects of delinquent behavior on friendship evolution

A multilevel approach is proposed to the study of the evolution of multiple networks. In this approach, the basic evolution process is assumed to be the same, while parameter values may differ between different networks. For the network evolution process, stochastic actor-oriented models are used, of which the parameters are estimated by Markov chain Monte Carlo methods. This is applied to the study of effects of delinquent behavior on friendship formation, a question of long standing in criminology. The evolution of friendship is studied empirically in 19 school classes. It is concluded that there is evidence for an effect of similarity in delinquent behavior on friendship evolution. Similarity of the degree of delinquent behavior has a positive effect on tie formation but also on tie dissolution. The last result seems to contradict current criminological theories, and deserves further study.     

Haplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matrices

Since exact determination of haplotype blocks is usually not possible, it is desirable to develop a haplotyping method which can account for recombinations. A natural candidate for such a method is haplotyping via phylogenetic networks or their simplified version: galled-tree networks. In earlier work we characterized the existence of the galled-tree networks. Building on this, we reduce the problem of haplotype inferring via galled-tree networks to a hypergraph covering problem for genotype matrices satisfying a combinatorial condition. Our experiments on actual data show that this condition is almost always satisfied when the percentage of minor alleles for each SNP reaches at least 30%.     

Approximate Greatest Descent Methods for Optimization with Equality Constraints

In an optimization problem with equality constraints the optimal value function divides the state space into two parts. At a point where the objective function is less than the optimal value, a good iteration must increase the value of the objective function. Thus, a good iteration must be a balance between increasing or decreasing the objective function and decreasing a constraint violation function. This implies that at a point where the constraint violation function is large, we should construct noninferior solutions relative to points in a local search region. By definition, an accessory function is a linear combination of the objective function and a constraint violation function. We show that a way to construct an acceptable iteration, at a point where the constraint violation function is large, is to minimize an accessory function. We develop a two-phases method. In Phase I some constraints may not be approximately satisfied or the current point is not close to the solution. Iterations are generated by minimizing an accessory function. Once all the constraints are approximately satisfied, the initial values of the Lagrange multipliers are defined. A test with a merit function is used to determine whether or not the current point and the Lagrange multipliers are both close to the optimal solution. If not, Phase I is continued. If otherwise, Phase II is activated and the Newton method is used to compute the optimal solution and fast convergence is achieved.     

The school class allocation problem—maximising friendship requests subject to diversity requirements

Friendship groups are an important element in both the social and academic well-being of school students, particularly in their younger years. Each year, school management has to assign students to a particular class in their new grade in junior school, and in doing so make and break friendship preferences as other criteria need to be satisfied in order to ensure diversity. This ongoing administrative task is time consuming and does not always result in the most equitable allocation. Coupled with the lack of transparency of the process, this can lead to teacher and parent frustration. This paper formulates and solves a mathematical programming model for this problem and shows that better solutions can likely be found in a fraction of the time using software that is freely available.     

Parties and networks: Stochastic models for relationship networks

This paper argues that parties and other gatherings are important for the development of friendship networks. It proposes a stochastic model for the evolution of networks over time, the distinctive feature of which is the party event. A party event occurs when a person in the network has a gathering and invites all of his/her friends who then also become friends. The Party Models discussed are all based upon this simple assumption. After formulating basic assumptions, various differential equations describing Party Models are derived. Subsequently several concepts useful for model analysis are defined and briefly explored. These include the concepts of potential, equivalence class form, and degenerate models. The penultimate section considers models for three person networks in some detail and with numerical illustrations. All extended mathematical arguments are placed in the Mathematical Appendix.     

Automatic identification of embedded network rows in large-scale optimization models

The solution of a large-scale linear, integer, or mixed integer programming problem is often facilitated by the exploitation of special structure in the model. This paper presents heuristic algorithms for identifying embedded network rows within the coefficient matrix of such models. The problem of identifying a maximum-size embedded pure network is shown to be among the class of NP-hard problems. The polynomially-bounded, efficient algorithms presented here do not guarantee network sets of maximum size. However, upper bounds on the size of the maximum network set are developed and used to show that our algorithms identify embedded networks of close to maximum size. Computational tests with large-scale, real-world models are presented.     

Markov network processes with product form stationary distributions

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Network robustness and irreversibility of information diffusion in Complex networks

Complex networks are characterized based on a newly proposed parameter, “degree of diffusion α”. It defines the ratio of information adopters to non-adopters within a diffusion process over consecutive penetration depths. Furthermore, the perfectness of a social network is evaluated by exploring different variations of α such as the reverse diffusion (α_reverse) and the random-kill-diffusion (RKD) processes. The analysis of α_reverse and RKD processes shows information diffusion irreversibility in small-world and scale-free but not in random networks. It also shows that random networks are more stable toward attacks, resulting a complete information diffusion process over the entire network. Finally, a real Complex network example, represented as a “virtual friendship network” was analyzed and found to share properties of both random and small-world networks. Therefore, it is characterized to be somewhere between random and small-world network models or in other words, it is a randomized small-world network model.     

More about empirical evaluation of formal theory†

The purpose of this discussion is to transform the implicit equilibrium assumption endemic to network analysis into an explicit instrument for such analysis. I propose a formal model that brings together Coleman's restriction of Walras’ general equilibrium model and recent developments in describing the “social topology” of a multiple network system of actors such that a class of relational equilibria is defined. The specific equilibrium expected in a system is a function of the previously existing stratification of actors in the system. Corresponding to multiple observed networks, the model generates multiple equilibrium networks. The structural analysis of the observed networks can therefore be repeated on the equilibrium networks so as to assess the extent to which the analysis would differ if the observed relations were actually in an equilibrium state. Numerical illustration is provided by an analysis of alternative relational equilibria in the system of elite experts in methodological and mathematical sociology as such a system existed in 1975.     

Gated Bayesian networks for algorithmic trading

This paper introduces a new probabilistic graphical model called gated Bayesian network (GBN). This model evolved from the need to represent processes that include several distinct phases. In essence, a GBN is a model that combines several Bayesian networks (BNs) in such a manner that they may be active or inactive during queries to the model. We use objects called gates to combine BNs, and to activate and deactivate them when predefined logical statements are satisfied. In this paper we also present an algorithm for semi-automatic learning of GBNs. We use the algorithm to learn GBNs that output buy and sell decisions for use in algorithmic trading systems. We show how the learnt GBNs can substantially lower risk towards invested capital, while they at the same time generate similar or better rewards, compared to the benchmark investment strategy buy-and-hold. We also explore some differences and similarities between GBNs and other related formalisms.     

On the cohomology of the free loop space of a 4- dimensional manifold

In this paper we consider a theorem of Feigin and Tsygan that is about the gereralized free product of a pushout diagram (Theorem 2 below) and try to show that it can be generalized, i e., the theorem is satisfied in the more general case than that they have stated. In order to do this, we formulate a conjecture stating the validity of such generalizatzon. To support the conjecture we use it in two different computations, and show that the results of these computations coincide with the results that C. Löfwall has proved in a different way.

I wish to thank J. E. Roos who called my attention to this problem. I am grateful to him because of his great help and good advice during the work on this paper. I wish to thank Ralf Fröberg, L Lambe, and C Löfwall for stimulating discussions.     

演员合作网的可重复连线模型

复杂网络中,除了会增加新节点和边之外,旧节点之间的相互作用关系强度也可能增加.本文以演员合作网为例,提出了一个可重复连线的模型,该模型结合了重复连线(即两节点之间可以有一条以上的边来反映强度的增加)和增长择优机理,更符合演员合作网的拓扑结构.通过计算机模拟和公式推导,该模型中节点的度分布显示出幂律尾部的特性,而且其衰减指数在一定条件下与实证研究结果是一致的.     

Infinite generalized friendship graphs

We give necessary and sufficient conditions for the existence of infinite generalized friendship graphs and show that there are 2° non-isomorphic ones of each admissible order c and chromatic number. Further we prove that such graphs and their complements are almost always regular of degree equal to the order and that various generalizations of the Friendship Theorem do not hold for infinite generalized friendship graphs.     

Institutional Logics from the Aggregation of Organizational Networks: Operational Procedures for the Analysis of Counted Data

We address some problems of network aggregation that are central to organizational studies. We show that concepts of network equivalence (including generalizations and special cases of structural equivalence) are relevant to the modeling of the aggregation of social categories in cross-classification tables portraying relations within an organizational field (analogous to one-mode networks). We extend our results to model the dual aggregation of social identities and organizational practices (an example of a two-mode network). We present an algorithm to accomplish such dual aggregation. Within the formal and quantitative framework that we present, we emphasize a unified treatment of (a) aggregation on the basis of structural equivalence (invariance of actors within equivalence sets), (b) the study of variation in relations between structurally equivalent sets, and (c) the close connections between aggregation within organizational networks and multi-dimensional modeling of organizational fields.