ASIST2006 Opening Plenary: Barabasi Open Plenary: Albert-László Barabási

Professor at Notre Dame


Erdos-Renyi Model (1960)
Looking at degree and degree centrality and Poisson distribution for a random network where everyone has the same degree.

They looked at the web and then looked at degree and found instead of a Poisson distribution, found a power law. Likewise, the highway system is Poisson and the air line paths are scale free/power law (published in Nature, 1999).

But highways, etc., are man-made. Does this apply in nature? Then looking at Metabolic Network and Protein Interactions networks we see that they are also scale-free.


Origins of scale-free networks
- what’s interesting is what the ties actually are
- Barabasi & Albert Science 286 (1999)

Growth and preferential attachment
Networks continuously expand by adding new nodes
New nodes prefer to connect to more connected pages (preferential attachment)
First mover advantage
Fitness k(t) – t^(ηa), a modifier like for a web page might include attributes like content

Robustness and Fragility
Albert, Jeong, Barabasi, Nature 406 (2000)
If you remove some nodes you end up with many components and lots of isolates… With a large scale free network, you can remove 90% of the nodes and the network is still functioning – unless you specifically attack the hubs.

Modularity
(if it can be clustered or if there are groups/subnetworks that can be defined)
He argues that a network can be both modular and scale free. He constructed a model to propose how it could happen. Mathematically, looking at the clustering coefficient C(k) ~ k^-1 where C(k) = #links/k(k-1)

Finding Overlapping communities inNetworks
Palla, ALB, Vicsek (nature) – a same node can be in multiple clusters.

How do communities change over time
Grow, contract, merge, split, birth, death
Small communities tend to be stable if members do not change over time. OTOH, large communities will only last if there is high turnover.

Viral Marketing
How can we use this network information for marketing?
If the information is given to hubs vs. if given to a random member of the network. (ok, so this is fairly new to network methods, but of course information diffusion and “opinion leaders” in marketing have been around for a while.

Visualizing clicks on a web site – Poisson process? No it’s bursty so it’s a scale free network and there’s a long tail

Looked at e-mail, library loan, cell-phone views – all scale free networks. Why? Probably because of prioritization of tasks instead of random execution of tasks. How do we see if this is a feature of our technology world, or something about us as humans? Look at Einstein and Darwin who were both avid letter writers. (Oliveria, ALB, Nature 2005). # of letters is power law, but more importantly, how long the letters sat on the desk also follows the power law.

www.nd.edu/~networks

Update: added tag

asist2006

Labels: asist2006

  ¶ 3:24 PM| |cites (technorati) |