The Role of Trends in Evolving Networks

Modelling complex networks has been the focus of much research for over a decade [1]-[3]. Preferential attachment (PA) [4] is considered a common explanation to the self organization of evolving networks, suggesting that new nodes prefer to attach to more popular nodes. The result is a broad degree distribution, found in many real world networks. Another feature present in observed real world networks is the tendency to build clusters, i.e., groups of tightly connected nodes. The traditional PA model does not reveal such a feature. In general, the PA model is driven by aging effects, i.e., the older a node, the higher the probability that a newly arrived node in the network connects to it. Clearly, there are other effects in networks like trends. A newly arrived node may become a very strong driver in a network, i.e., becoming a trend. Our latest paper describes a model, in which we incorporate the concept of trendiness. Namely, in trending networks, newly arriving nodes may become central at random, forming new clusters (groups). In particular we show that when the network is young it is more susceptible to trends, but even older networks may have trendy new nodes that become central in their structure.

The Model (TPA)
We assume an evolving network where in each time step a node is added with m links. We define the network’s tendency to adhere to trends by r. Then a node with degree k that has acquired \Delta k links in the last step will acquire new links in monotonically increasing rate that is a function of k + r \Delta k. The more trendy is the network, the bigger is the effect of small changes. Hence, new nodes are more likely to attach to nodes that either have a high degree or are gaining a momentum in the growth of the number of new links, and hence are trendy.

Like in the PA model we start with m_{0} nodes. Then, at each step, a new mode with m \le m_{0} links is addes. The other ends of the links are chosen with a probability that correlates with node’s importance, denoted by its relative a relative weight W_{i}.

\Pi(W_{i}) = \frac{W_{i}}{\sum_{j}W_{j}}.

Where W_{i} = k_{i} + r \Delta k_{i}, and \Delta k_{i} is the recent growth in the degree of node $i$ degree. We have chosen the most simple way for \Delta k_{i} = k_{i}(t) - k_{i}(t-1). The total weight at time $t$ is therefore 2mt + mr.
The striking feature of the model is the dynamics of young trending networks, namely, when r \gg N with $N$ the number of nodes in the network. When the growth model allows for the addition of one node at each step, N \sim t. Consequently, for very trending young networks, we get:

\Pi(t) = \frac{W_{i}(t)}{\sum_{j}W(t)} \rightarrow r^{-0.5}.

Showing that newly arriving nodes have a similar probability of becoming important as older nodes in the network. This model property has to be contrasted with the PA model, which favours older nodes in the network to become more dominant.

The following plot shows a network generated by the TPA model. The labels correspond to the node’s arriving time step. It is clearly visible that nodes arriving even late have the chance to become a trend, i.e., the center of a cluster.

r2000

The full paper can be downloaded here.

[1] D. Watts and S. Strogatz, “Collective dynamics of samll-world networks, Nature, vol.393, pp.440-442, 1998.
[2] R. Albert and A. Barabasi, “Statistical mechanics of complex networks”, Reviews of modern physics, vol 74, no 1., p.47, 2002.
[3] M. Newman, A. Barabasi, and D. Watts, “The strucutre and dynamics of networks.”, Princeton University Press, 2011.
[4] A. Barabais and R. Albert, “Emergence of scaling in random networks”, Science, vol. 286, no. 5439, pp. 509-512, 1999.

About Blattner

Head Laboratory for Web Science.
This entry was posted in algos, complex_system, data and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s