Hi all!
I want to draw a social graph structure following the famous Barabasi-Albert model of scalefree networks (think PageRank).
A really simplified adaptation of the BA model of ‘preferential attachment’ is: “Each new node is connected to m of the existing with a probability that is biased so that it is proportional to the number of links that the existing node already has.” http://ow.ly/1S7ZU [ow.ly]
The algorithm goes as follows:
0. initial randomly distributed set of points, with edges between nearest neighbor point pairs
1. randomly add points one by one and add edges between nearest neighbor point pairs
2. for each new edge, the Probability of a new edge equals the number of edges (K degree) of the (for us ‘nearest’) neighbor i proportional to the total number of edges:
P(new edge attachment) = K(neighbor i) / K(total)
3. points have a life expectancy proportional to the number of edges they each have (so points with more edges live longer and in turn aggregate more edges in a positive feedback loop)
Any ideas how to implement this?
Gon
Social graph
2719 1 1- gonzifroni
- Member
- 29 posts
- Joined: Sept. 2007
- Offline
- Antoine Durr
- Member
- 321 posts
- Joined: July 2005
- Offline
Either with L-Systems, or as a particle system with controlled splitting based on the external data. The latter is probably more in line with how the algorithm works. For example, the split POP can use the external data to decide if the given particle should split. On the split, you can determine where the splitees should start, how many there should be, etc.
-
- Quick Links