Social-circles network model

From Wikipedia, the free encyclopedia

The generative model of feedback networks ^[1], ^[2] studied by White, Kejžar, Tsallis, Farmer, and White, or social-circles network model, defines a class of random graphs generated by simple processes that are common to edge formation and feedback loops in social circles. This class is distinct from the small-world network and the scale-free network models but also captures many of the characteristics of real-world networks.

1 Highlights
2 Rationale
3 Results
4 Degree Distributions
5 Bibliography
6 Links
7 Notes

[edit] Highlights

A feedback network is one where active nodes or agents send tokens or communications through their network to help locate potential partners for new ties.
When a previously unconnected partner is located given constraints of distance a new tie is formed, creating a feedback loop.
Failing to locate a partner within the network, the active node engaged in partner selection recruits a new partner from outside the existing network and forms a tie.
Like many real-world networks, feedback networks modeled by this process evolve large networks with cohesive ties (social circles). In this way, small worlds with cohesive subgroups and relatively short distances may be generated, scale-free networks may be generated, or a variety of other network topologies may be generated.
The generative feedback network model simulates these processes and their network outcomes as new nodes and edges are added to an initial network.
Only three parameters are used to govern network formation in this probabilistic generative model. These govern levels of node activity, distance decay in how soon network traversal fails to find a partner, and the extent to which local hubs are used in network traversal.
The model provides an explanation for how hubs are formed in networks, how well-traveled edges are formed, how cycles and cohesion are formed, and how other features of real-world networks may result from different combinations of three basic network parameters.
Empirical network data can be fitted to the parameters of the general model.

[edit] Rationale

A social-circles network models by a graph-generating process the formation of cohesion and dispersion in connected networks as a function of acitvity and feedback. The process begins with a single node. The next events in the evolution of the network are that: (1) a node is chosen randomly (proportional to the number of current links of each node raised to power alpha) to emit a feedback token, (2) the token attempts to travel by a non-circular path through the current network by choosing its next neighbor randomly, proportional to the number of edges of the neighbor minus the node already traversed, raised to power gamma; (3) the token travels through the network until it reaches a random distance d, proportional to 1 over d raised to a power beta, and failing that, the source node that originated the token gains an edge to a node that is added to the network (dispersion of edges), but if the token succeeds in reaching a target at distance d, a new 'feedback' edge is added between the source and the target.

The three parameters of the model are alpha, beta, gamma. The notion of 'feedback' in this model is very general and may involve intentionality on the part of source nodes as agents looking for a partner or simply nodes in a network emitting signals randomly that contain information that may enable the source and target to lock into a feedback relation, represented by the formation of a new edge. Whether searches or signals have the capacity to locate a target in an existing network is affected by the current size and topology of the network, the distance decay (beta) in traversal, and the intelligence (gamma) exhibited in the method of search. Failure to locate targets results in a generic substitution (new node and an edge connecting to it), like looking in the phone book for a doctor rather that asking for a referral.

[edit] Results

Social-circles network simulation with varying model parameters results in a variety of networks whose topology in terms of network density, clustering, cohesion, and degree distribution varies in ways that resemble the variety of real-world networks. Study of the degree distributions and edge-traversal frequencies shows fit to the statistical distributions of Tsallis entropy, familiar to nonextensive physics. This provides a baseline test of the model to real-world networks, one that contrasts with that of the scale-free network, for which one baseline test is whether the degree distribution follows a power law. The Tsallis entropy distribution asymptotes to a power law for large degree but bends toward the exponential distribution in the lower part of the degree distribution.

[edit] Degree Distributions

Parameters $α,β,γ$ in the social circles model are shown to generate networks with degree distributions that fit a general family of curves that combine power-law with exponential tendencies. The density function for degree $k$ in this family, with parameters $δ,κ, q$ , and $p 0$ , is given by:

$p(k)=p_0k^\delta e_q^{-k/\kappa}$

where the q-exponential function $e^{-x}_q$ with parameter $q$ is defined as

$e^{-x}_q = (1+(1-q)x)^{1/(1-q)} (e_1^x = e^x)$

The function for $p (k)$ arises naturally as the solution of the equation $d k / d t = k q$ , which is $\kappa=e^{-x}_q = [1+(1-q) a t]^{1/(1-q)}$ . For the case where $q = 1$ , $k = e a t$ .

In this generalization, the parameters $δ,κ, q$ , and $p o$ of the fitted models, which may also be applied to the degree distributions of empirical networks, were found to closely approximate 1-to-1 functions of the generating parameters, as given by the approximations

δ = - 1.5α

q = 1 + .64α + 6αγ(β - 1) 2

κ = 235γ(1 - α)(β - 1)

p o = 2 + α / 4 - β - 1.3γ

These allow approximate solutions for the generating parameters that fit observed empirical degree of networks:

α = - 2δ / 3

β = 3 / 2 + p o / 2 + q / 9

γ = 5 | (q / k) - .5 | 1 / 2 + 5 p 0 + 11 q / k

The last of these approximations (for $γ$ ) is the least accurate (more precise estimates may yet be found). The authors of the paper have provided a more exact optimal matching between the four parameters fitted from empirical degree distributions of actual networks (assuming they follow the $q$ -exponential) in spreadsheet form.^[3] This makes the social circles model a prime candidate for accounting for the degree distributions of empirical networks in terms of a generative network model with the three parameters $α,β,γ$ : activity bias of agents, distance decay, and navigability of the network. Maximum likelihood estimates of the four $δ,κ, q$ , and $p o$ parameters for empirical networks and goodness-of-fit tests can establish the statistical relationship between model and data.