Social-circles network model
Encyclopedia
The generative model of feedback networks , studied by White
, Kejžar
, Tsallis
, Farmer
, 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 in network analysis
but also captures many of the characteristics of real-world social network
s. The implications of this type of model are carried further in Thurner, Kyriakopoulos and Tsallis, 2007, Unified Model for Network Dynamics Exhibiting Nonextensive Statistics Phys. Rev. E 76, 036111 (2007) (8 pages).
and dispersion
in connected networks as a function of activity 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 than asking for a referral.
, 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.
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 probability density function for degree 
in this family, with parameters 
, and 
, is given by:
where the q-exponential function
with parameter 
is defined as
The q-exponential function arises naturally as the solution of the equation
, which is 
. For the case where 
, 
. The function is related to the stationary solution of a nonlinear Fokker-Planck equation known as the porous medium equation. It describes correlated diffusion known as Darcy's law
, the scientific basis of fluid permeability used in the earth sciences. This is a constitutive equation that describes the flow of a fluid through a porous medium as formulated by Henry Darcy to describe results of experiments on the flow of water through beds of sand (see references [2,3,4]). In the density function,
coincides with 
if and only if 
; 
is a characteristic degree. In a generalization of the water-flow analogy, the density function for degree would reflect a q-exponential component for which q=1 is omnidirectional flow, and as q increases there is initially a steep low-dimensional gradient that changes to flat and high dimensional as q grows to infinity. The other component corresponding to 
would reflect a characteristic magnitude of flow also affected by q. A loose analogy is to traders whose activities etch the routes of their commercial networks, amplified by gradient intensities and the heterogeneity of terrain.
, and 
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
These allow approximate solutions for the generating parameters that fit observed empirical degree of networks:
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 
-exponential) in spreadsheet form. 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 (MLE) of the four
, and 
parameters for empirical networks and goodness-of-fit tests can establish the statistical relationship between model and data. Shalizi (2007) provides an MLE procedure for the Pareto II or q-exponential parameter fitting.
In short, the generative feedback model has realistic and nicely continuous characteristics, and these simulations show no evidence that the density function for degree k is not the correct function.
Douglas R. White
Douglas R. White is an American complexity researcher , social anthropologist, sociologist, and social network researcher at the University of California, Irvine.-Biography:...
, Kejžar
Nataša Kejžar
Nataša Kejžar is an olympic swimmer, born October 14, 1976 in Jesenice, Slovenia, Yugoslavia. She studied at Faculty of Computer and Information Science, Ljubljana and achieved her PhD degree in Statistics in 2007. She is...
, Tsallis
Constantino Tsallis
Constantino Tsallis is a naturalized Brazilian physicist working in Rio de Janeiro at CBPF, Brazil. He was born in Greece, and grew up in Argentina, where he studied physics at Instituto Balseiro, in Bariloche. In 1974 he received a Doctorat d'Etat et Sciences Physiques degree from the University...
, Farmer
J. Doyne Farmer
J. Doyne Farmer is an American physicist and entrepreneur, with interest in chaos theory and complexity. He is a professor at the Santa Fe Institute. He was also a member of Eudaemonic Enterprises.-Biography:...
, 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
Small-world network
In mathematics, physics and sociology, a small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps...
and the scale-free network
Scale-free network
A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...
models in network analysis
Network analysis
Network analysis can refer to:* Analysis of general networks: see Network theory.* Electrical network analysis see Network analysis .* Social network analysis.You may also be interested in Network planning and design...
but also captures many of the characteristics of real-world social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s. The implications of this type of model are carried further in Thurner, Kyriakopoulos and Tsallis, 2007, Unified Model for Network Dynamics Exhibiting Nonextensive Statistics Phys. Rev. E 76, 036111 (2007) (8 pages).
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 worldsWatts and Strogatz modelThe Watts and Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their joint 1998 Nature paper...
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 cohesionStructural cohesionStructural cohesion is the sociological conception of cohesion in social groups. It is defined as the minimal number of actors in a social network that need to be removed to disconnect at least two actors in the remaining group. It is thus identical to the question of the node connectivity of a...
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.
Rationale
A social-circles network models by a graph-generating process the formation of cohesionStructural cohesion
Structural cohesion is the sociological conception of cohesion in social groups. It is defined as the minimal number of actors in a social network that need to be removed to disconnect at least two actors in the remaining group. It is thus identical to the question of the node connectivity of a...
and dispersion
Star network
Star networks are one of the most common computer network topologies. In its simplest form, a star network consists of one central switch, hub or computer, which acts as a conduit to transmit messages...
in connected networks as a function of activity 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
Distance decay
Distance decay is a geographical term which describes the effect of distance on cultural or spatial interactions. The distance decay effect states that the interaction between two locales declines as the distance between them increases...
(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 than asking for a referral.
The generative model
At each step three stochastic processes are run. A node i is selected, a distance d (an imaginary number of steps to get to a searched node j) is chosen, and the search path of distance d is generated.- A node i is selected with a probability proportional to its degree
-
- A distance d is chosen with the probability
-
- where d represents the number of steps necessary to create a new cycle. If the number of steps cannot be concluded, a new node with a new edge is added.
- A search path of length d is generated. At a given moment a node r is a current node on the path. The next node is selected among the neighbors of r that were not yet visited. The probability of selecting a certain neighbor (say l) is proportional to their 'unused degree'. The 'unused degree', u(l), is considered a degree of the node from which all the already visited neighbors are subtracted. The probability is given by
-
Results
Social-circles network simulation with varying model parameters results in a variety of networks whose topology in terms of network density, clusteringClustering coefficient
In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties...
, cohesion
Structural cohesion
Structural cohesion is the sociological conception of cohesion in social groups. It is defined as the minimal number of actors in a social network that need to be removed to disconnect at least two actors in the remaining group. It is thus identical to the question of the node connectivity of a...
, and degree distribution
Degree distribution
In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.-Definition:...
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
Tsallis entropy
In physics, the Tsallis entropy is a generalization of the standard Boltzmann-Gibbs entropy. In the scientific literature, the physical relevance of the Tsallis entropy is highly debated...
, familiar to nonextensive physics
Constantino Tsallis
Constantino Tsallis is a naturalized Brazilian physicist working in Rio de Janeiro at CBPF, Brazil. He was born in Greece, and grew up in Argentina, where he studied physics at Instituto Balseiro, in Bariloche. In 1974 he received a Doctorat d'Etat et Sciences Physiques degree from the University...
. This provides a baseline test of the model to real-world networks, one that contrasts with that of the scale-free network
Scale-free network
A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...
, for which one baseline test is whether the degree distribution follows a power law
Power law
A power law is a special kind of mathematical relationship between two quantities. When the frequency of an event varies as a power of some attribute of that event , the frequency is said to follow a power law. For instance, the number of cities having a certain population size is found to vary...
.
The Tsallis entropy
Tsallis entropy
In physics, the Tsallis entropy is a generalization of the standard Boltzmann-Gibbs entropy. In the scientific literature, the physical relevance of the Tsallis entropy is highly debated...
distribution asymptotes to a power law for large degree but bends toward the exponential distribution
Exponential distribution
In probability theory and statistics, the exponential distribution is a family of continuous probability distributions. It describes the time between events in a Poisson process, i.e...
in the lower part of the degree distribution.
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 probability density function for degree in this family, with parameters , and , is given by: where the q-exponential function
with parameter is defined asThe q-exponential function arises naturally as the solution of the equation
, which is . For the case where , . The function is related to the stationary solution of a nonlinear Fokker-Planck equation known as the porous medium equation. It describes correlated diffusion known as Darcy's lawDarcy's law
Darcy's law is a phenomenologically derived constitutive equation that describes the flow of a fluid through a porous medium. The law was formulated by Henry Darcy based on the results of experiments on the flow of water through beds of sand...
, the scientific basis of fluid permeability used in the earth sciences. This is a constitutive equation that describes the flow of a fluid through a porous medium as formulated by Henry Darcy to describe results of experiments on the flow of water through beds of sand (see references [2,3,4]). In the density function,
coincides with if and only if ; is a characteristic degree. In a generalization of the water-flow analogy, the density function for degree would reflect a q-exponential component for which q=1 is omnidirectional flow, and as q increases there is initially a steep low-dimensional gradient that changes to flat and high dimensional as q grows to infinity. The other component corresponding to would reflect a characteristic magnitude of flow also affected by q. A loose analogy is to traders whose activities etch the routes of their commercial networks, amplified by gradient intensities and the heterogeneity of terrain.Retrofitting
The parameters, and 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
These allow approximate solutions for the generating parameters that fit observed empirical degree of networks:
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 -exponential) in spreadsheet form. 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 likelihoodMaximum likelihood
In statistics, maximum-likelihood estimation is a method of estimating the parameters of a statistical model. When applied to a data set and given a statistical model, maximum-likelihood estimation provides estimates for the model's parameters....
estimates (MLE) of the four
, and parameters for empirical networks and goodness-of-fit tests can establish the statistical relationship between model and data. Shalizi (2007) provides an MLE procedure for the Pareto II or q-exponential parameter fitting.Replication and extensions
Kejžar in 2007 [5] replicated these results by simulating feedback networks up to N=5000 nodes, extended the findings to:- Degree distributions for directed edges (indegree, outdegree). These were similar to those of the undirected model, especially for
but differed toward higher q when 
- Densification. Growth of edges relative to nodes is initially linear, but soon changees to approximate a slightly superlinear power-law (for
, for example, where e are edge numbers and n numbers of node). Even with 1 billion nodes, however, this is scarcely more than an average degree of 5. Up to 6000 nodes, the average degree is less than two. For large degrees, however, the degree distribution approaches a power law with an exponent 
. Densification is a natural consequence. - Average shortest paths. If l is the average shortest path and n the number of nodes, l shrinks with n if
but rises if 
and a weighted sum of 
determines the crossover (low 
, high 
has the most rapid shrinkage). In every case there tends to be a "shrinking limit" as 
- Variance of shortest paths. Most of the shortest paths between nodes approach the "shrinking limit."
In short, the generative feedback model has realistic and nicely continuous characteristics, and these simulations show no evidence that the density function for degree k is not the correct function.
External links
- Simulated data in a Pajek Network Project *.paj file for 1250 nodes paramaters 0-2-0
- Walk-through of a network simulation, edge by edge with the same parameters
- http://www.insna.org INSNA International Network for Social Network Analysis—professional association of network analysts