Preferential Attachment

In class on Oct 23rd, two students were brave enough to show off their “Facebook report” from Wolfram Alpha. Thank you! In both cases, I was struck by how highly clustered the set of friends was. In other words, a large fraction of the friends were also friends of each other, implying a very high clustering coefficient for each of the two students.

After the “Facebook report” activity, I showed a demonstration of the preferential attachment model (also called the Barábasi-Albert model) in Netlogo. Here is a pretty clear description of how the model works (copied from Netlogo’s page on preferential attachment):

The model starts with two nodes connected by an edge. At each step, a new node is added. A new node picks an existing node to connect to randomly, but with some bias. More specifically, a node’s chance of being selected is directly proportional to the number of connections it already has, or its “degree.” This is the mechanism which is called “preferential attachment.”

Homework for Tuesday, Oct 30: Read “The Seventh Link” on “Rich Get Richer.” Come prepared to discuss this reading in class. Also, play with the Netlogo demonstration of the preferential attachment model and answer the following questions:

  • Suppose you use the model to build a graph with 1000 nodes. What is the average degree of a node in this graph?
  • What is the frequency of nodes of degree 1, degree 2, degree 3, and degree 4?
Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s