Emergence of Scaling in Random Networks

Networks,Reading,Science — Zac Townsend @ October 31, 2012 10:12 am

This article by Barabasi and Albert provide an explanation for why the distribution of links over nodes in many real-world networks follow a power-law distribution. Power-law distributions are defined by a concentration of the density in a small number of units and then a long-tail.

The distribution function of connectivities for various large networks. (A) Actor collaboration graph with N=212,250 vertices (B) WWW, N=325,729 (C) Power grid data, N =4941, . The dashed lines have slopes (A)=2.3, (B)=2.1 and (C)=4

After going through some example of networks with complex topologies--everything from neurons to the World Wide Web--they note that networks have traditionally been described by the random network model of Erdos and Renyi (the "ER" model). But, the ER model (and the WS model) is not up to the task of explaining the scale-free power law distributions that they find by "exploring several large databases describing the topology of large networks that span fields as diverse as the WWW or citation patterns in science."

More precisely, the authors find that independent of the system by which the networks are created, that the probability P(k) that a node has k links follos P(k) \sim k^{- \gamma}. They explain these distributions by developing a model that includes growth and preferential attachment--in short, 1) that networks start small and grow larger and 2) that no matter if a) because early nodes (those that exist when the network is young) have more random chances to be linked to new nodes or because b) there is "preferential attachment" made to those nodes that are already popular, that there will be some winners with many more links than most other nodes.

Why do the ER and WS models not accurately explain the power-law phenomena? Both models start with a fixed number of nodes and then randomly connect them (ER) or reconnected (WS), whereas this model takes explicit account of the growing number of nodes that occurs in most real world networks. Additionally, the two random network models assume that the probability that any two nodes are connected is random and uniform, whereas this model includes preferential connectivity:

For example, a new actor is most likely to be cast in a supporting role with more established and better-known actors. Consequently, the probability that a new actor will be cast with an established one is much higher than that the new actor will be cast with other less-known actors.

So, how does their model work? It begins with some small number of nodes and then keeps adding new nodes with the probability that the new nodes will be connected to all the previous nodes weighted by the previous nodes popularity. In their language,

  1. To incorporate the growing character of the network, starting with a small number (m_0) of nodes,
    at every time step they add a new node with m(m_0) links, so the new node connects to $m$ different vertices already present in the system.
  2. To incorporate preferential attachment, they assume that the probability \Pi that a new node will be connected to node i depends on the connectivity k_i of that node, so that \Pi (k_i)=\frac{k_i}{\sum_jk_j}.

They continue by developing slight variants of this model--one that assumes growth but not preferential treatment and one that assumes preferential treatment but not growth--and show that neither is sufficient to explain the emergent scale-free power law distributions seen in real-world networks.

Because of preferential treatment, early gains are quite important and older nodes increase their connectivity at the expense of the younger ones. This leads to some nodes "that are highly connected, a “rich-get-richer” phenomenon that can be easily detected in real networks."

Identity and Search in Social Networks

Networks,Reading,Science — Zac Townsend @ October 30, 2012 10:48 am

This articles develops a model for explaining how "ordinary" individuals can search through their social networks and send messages to distant people they do not know.

Travers and Milgram (Sociometry, 1969) ran a experiment where they asked people in Omaha, NE to try to get a letter to randomly selected people in Boston. The Nebraskans were to do this by mailing the letter to an acquaintance they thought would be closer to the target. "The average length of the resulting acquaintance chains for the let ters that eventually reached the target (roughly 20%) was about six." These results suggest that short paths exist between many people and that ordinary people can find those paths. This is pretty cool because although most people know there friends, they don't know there friend's friends (imagine a pre-facebook world). The authors of the article I am reading today call the ability to find targets "searchability." They question the accuracy of previous studies who tried to model social network using 1) hubs or highly connected people that you need only reach and then you will reach the target or 2) geometric lattices (which often have some assumption that every node has the same number of edges, see regular networks from yesterday's post) because neither of these network types, however, is a satisfactory model of society. (As an aside, models should not be judged on whether or not their assumptions comport with reality but on whether they make useful and accurate predictions, see Gary King or Milton Friedman on this point).

The authors build a model from "six contentions about social networks":

  1. People have identities and social groups are collections of identities.
  2. People break their society up in to hierarchies. They use an example of a specialized subgroup with an academic department that in turn is within a university. Formerly they put an upper bound on group size near one hundred, formally g \approx 100. They define the similarity between two individuals i and j as x_{ij}, where x_{ij}=1 if they are in the same group (=2 if they are in the same department in the example above).
  3. Group membership is the the primary basis for social interaction and thus you're more likely to know someone the closer you are to being in the same group. The chance that two people are acquaintances decreases when the groups they belong to are more dissimilar. To build their social network, they keep making connections between people until the average numbers of friends equals z. They make these links by randomly choosing an individual, then choosing a link distance, x, to add to that person with p(x)=c\cdot e^{\alpha x}, and then by choosing a random person in that other level that is x levels away and making the link. \alpha is a "tunable" parameter and is a measure of homophily--the tendency of similar people to group together--in the created social network.
  4. People can belong to different hierarchical groups (I am a member of the City of Newark workforce, the Brown alumni, the Manhattan democrats, Brooklyn) and it is assumed these groups are independent. This is a standard assumption but you can see in my group membership alone that Brown and Brooklyn likely aren't wholly statistically independent. In this way a person's identity is defined by the position people have in various hierarchies defined in the model, represented by the H-dimensional vector \vec{v}_i, where where v_i^h is the position of node i in the h^{th} hierarchy, or dimension. Each node is randomly assigned a location in the various hierarchies and then the links are made as is indicated in point three above (I think it would have made more sense to explain this point than that one).
  5. People construct a social distance to perceive the similarity between themselves and others. This is here defined as the minimum distance that exist between nodes across all hierarchies, or y_{ij}=min_h x^h_{ij}. It is interesting to note that "social distance violates the triangle inequality ... because individuals i and j can be close in dimension $h_1$, and individuals j and k can be close in dimension $h_2$, yet i and k can be far apart in both dimensions. A simple example might be to use my dad as individual j, me as individual i, and one of my dad's work colleagues at Mt. Sinai as k. Although my dad and I are in the same family and he and his co-worker have the same occupation (x_{ij}=x_{jk}=1) the co-worker and I are quite socially distant.
  6. Individuals are only aware of their immediate network across all hierarchies, so that if a person forwards a message to a single neighbor that person does not know how much closer, if at all, the neighbor is to the intended recipient.

With this model, "[i]ndividuals therefore have two kinds of partial information: social distance, which can be measured globally but which is not a true distance (and hence can yield misleading estimates); and network paths, which generate true distances but which are known only locally."

With this model setup, they show that a greedy algorithm (the same as the one Milgram suggests) can efficiently direct a message to a receipt in a short number of steps.

They do some analysis that is worth noting. First, they point out (apparently against the previous literature) that the average length of a message chain, defined as the metric <L> has to be short in an absolute sense. The message chain length cannot scale with population n because of at each point there is a failure/termination rate of 25% (i.e. one and four people get the letter and do not forward it at all). Secondly, through some simple math they show that with a termination rate of 25% and a success rate fixed at above 5% that the average message length chain, <L> must be less than 10.4 independent of population size. With this, they can create diagrams of the parameter space in H and \alpha that meets that requirement. That is, they can create a graph of all the possible hierarchy number and homophily parameters that meet that requirement in <L>, thus:

Our main result is that searchable networks occupy a broad region of parameter space (\alpha ,H) which [...] corresponds to choices of the model parameters that are the most sociologically plausible. Hence our model suggests that searchability is a generic property of real-world social networks.

Collective Dynamics of ‘Small-world’ Networks

Networks,Reading,Science — Zac Townsend @ October 29, 2012 11:50 am

This article explores the dynamics of a network that is somewhere between regular and random.Regular networks are those where every node has the same number of connections. On the other hand, random networks are those that are built by introducing new nodes and randomly assigning edges between the new nodes and the old nodes with some probability, p (see the Erdos-Renyi model).

This paper "interpolates" between these two models by starting with a regular network (a ring lattice to be precise) and then rewiring each edge at random with probability p; in this way the graph is "tuned" between regular (p=0) and complete disorder / randomness (p=1).

To continue, we have to understand two measures that are often used in network theory: L(p) and C(p). L(p) is the average shortest length between all pairs of nodes. That is, if you find the shortest path between all pairs of nodes and then you take the average of those shortest paths you get L(p). C(p) is the clustering coefficient and is a measure of how many links exist between nodes divided by the number of possible such links.

For friendship networks, these statistics have intuitive meanings: L is the average number of friendships in the shortest chain connecting two people; C_v reflects the extent to which friends of v are also friends of each other; and thus C measures the cliquishness of a typical friendship circle.

The p=0 case is a "highly clustered, large world where L grows linearly with n" while the p=1 case is a "poorly clustered, small world where L grows only logarithmically with n". The key insight here is that allow it appears form these end points that large C and large L (and small C and small C) would always be associated from this simple analysis, it turns out that there is a "broad interval" where things stay clustered but the average length between nodes (L(P)) drops quickly. It's a "small world" because as you move, even just a little but, from a regular network to a random one there are introduced "short cuts" between groups that decreases the length: "The important implication here is that at the local level (as reflected by C(p)), the transition to a small world is almost undetectable."

The rest of the paper (Nature articles are quite short) shows three empirical examples fit this "small world" network model--IMDB film actors, the power gift, and the neural network of a nematode worm. The paper then finishes testing the implication of the network on a simulated disease outbreak where they show that 1) the smaller the L(p) of a network the faster the infection effects the entire population, 2) That a network just needs to be a little not regular for L(p) to drop significantly and 3) If it's a small world disease spread much more quickly than previous models suggest.

We hope that our work will stimulate further studies of smallworld networks. Their distinctive combination of high clustering with short characteristic path length cannot be captured by traditional approximations such as those based on regular lattices or random graphs. Although small-world architecture has not received much attention, we suggest that it will probably turn out to be widespread in biological, social and man-made systems, often with important dynamical consequences.