Annual 06 Plenary Session

From ASISTwiki

Plenary session - Albert-Laszlo Barabasi "The Architecture of Complexity"

(These are Ellen's notes; all errors are hers.)

Examples of networks: Internet, organizations, economic networks (eg. business ties), terrorist networks

How to think about networks? Erdos-Renyi model (1960) - democratic, random Are real networks random? Probably not - people are brought together in groups (towns, cities, organizations, families, etc.)

Consider the World Wide Web nodes = documents links = hypertext link -used a robot to create a map of a subset of the web for study -expected a Poisson distribution, but found that it followed the power law instead

Real-world networks: US highway system has a Poisson distribution US airline system has power law distribution. This sytem has a few major hubs, some smaller hubs, and many many tiny nodes. Example of a scale-free network.

Other scale-free networks: the Internet protein interaction the metabolic network Swedish sex-web (study of numbers of sexual partners)

Origin of scale-free networks - growth and preferential attachment 1) networks continuously expand by addition of new nodes - growth (add a new node with m links) 2) new nodes prefer to link to highly connected nodes - preferential attachment

How can late starters become hubs? Scale-free model has first mover advantage Real systems - nodes compete for links - finess High fitness notes will increase faster than low fitness nodes and therefore late starters can catch up - "fit-get-rich" Bose-Einstein condensation - hub and spokes model - some fitness distributions allow for this

Robustness - whether network maintains function when nodes break down. However, a network can be both robust and fragile - for example, the internet is vulnerable to attacks on hubs.

Modularity - real networks are fragmented into groups or modules. How to construct a scale-free and modular network? Clustering coefficient. Small nodes have a high clustering coefficient.

How to find modules? Communities grow, contract, merge, split, form, and die. Small communities have long life if members remain constant. Large communities have long life if members change constantly.

Viral marketing uses modularity - if something starts at a hub it will spread very quickly.

Barabasi looked at a portal in Hungary, [1]. Looked at visitation pattern for new site items. Modeled a user having 26 clicks/day, assumed Poisson distribution, and predicted typical decay time for a news idem of about 36 minutes. However, observed decay time was about 36 hours. Then looked at one person's click pattern - activity comes in bursts, not at a constant rate -- fits power law, not Poisson distribution. Same burst behavior for email, library loans, printing, web views, cellphone calls.

Why do bursts follow power law? Consider how you approach a to-do list. Randomly? Probably not. First-in, first-out? Good for pizza orders but not ideal for ordinary to-do list. Prioritize? This leads to a power law distribution.

Is this burst behavior the result of modern technology (computers, cellphones?) Looked at the correspondence habits of Darwin and Einstein. Response time to letters followed the power law.

So: science collaboration, WWW, language, cell phone cals, Internet, citation patters are all examples of scale-free networks. Open question is how these networks are used.

Papers online at [2]

Q&A Page Rank - not based on network science, but functions by giving hubs of network a higher weight.