Caveman World or Solaris or in between them - the birth of alpha model

The alpha model was one of the primitive attempt to model real-world social network. Before the proposition of small-world model by Watts-Strogatz, this model was one of the first attempt by Watts and Strogatz to really answer the question "What are the most general conditions under which the elements of large, sparsely connected network will be close to each other? " The modeling of the alpha graph makes two basic generalizations:

1) A network is represented purely in terms of connections between its elements i.e., whatever combination of factors makes people more or less likely to associate is
accounted for and represented by the distribution of those associations that actually form. Further, it also assumes all such connections to be symmetric and equally significant.

2) The likelihood of a new connection being created is determined by already existing connection pattern i.e., the current friends of a person determines to some extent the new friends of a person.

But how is new connections being formed? Is it caveman-like or is it solaria or in between them ?

The Caveman World:

"Everybody you know knows everybody else you know but no one else". So, an absence of mutual acquaintances among individuals means they live in different "caves", thus they will probably never meet. But if an individual has even one common friend implies that they live in the same community, move in the same social circle and so are very likely to become acquainted.

The Solaria:

The other extremity is the world of solaria. The name is after the planet "Solaria" from famous Issac Asimov novel where future humans live in isolation and interact across planets through computers and robots. In Solaria, the influence of existing friendship on new friendship links is indistinguishable from random chance i.e., social history of individuals are irrelevant to their future. Even if two people happen to have many friends in common, they are no more or less likely to meet than if they have none.

The real world social networks lie somewhere in between "caveman" and "solaria". To model the real world, one requires the following features in the algorithm for constructing such graphs

a) At one extreme (caveman world), the tendency of two unrelated people to get connected is very small. Once they share just one common friend their tendency to become acquainted becomes immediately very high and stays that way regardless of how many additional mutual friends they have. (see fig 1)

Fig.1 : Two extremes. in the top curve (caveman world) even a single mutual friend implies that A and B are highly likely to meet. In bottom curve (solaria) all interactions are equally likely, regardless of how many friends A and B have in common.

b) At the other extreme (solaris), having a very large number of mutual friends has very little effect on people's tendency to interact. Under almost all circumstances,
they interact randomly. (see fig 1)

c) In between these two extremes, the curves can take any one of an infinite number of intermediate forms by tuning a model parameter alpha where alpha = 0 corresponds to caveman world and alpha = infinite corresponds to solarian world (see fig 2).

Fig2 : Between two extremes, a whole family of interaction is possible , each one specified by tunable parameter alpha. When alpha = 0, it is caveman world and when alpha = infinite, it is solaria

To satisfy such constraints, one need to devise a metric which is the following:
where R i,j is the measure of tendency of vertex i to be connected with vertex j. (0 if already connected)
m i,j is the no. of vertices adjacent to both i and j
k is the average degree and p is the probability of an edge (i,j) being existing

Given n, k and alpha.

The algorithm is as follows:
1) Choose a vertex i uniformly at random.
2) For every other vertex, compute R i,j.
3) Sum the R i,j over all j's and normalize each to get P i,j which is the probability that i will connect to j
4) Generate a random number in [0,1]. If it corresponds to say, j*
5) connect i to j*.

Repeat until n.k/2 number of edges are formed.