The New Science of Networks
How is the World Wide Web organized? How are networks of friends organized? The interesting book, Linked: The New Science of Networks, by Albert-Laszlo Barabasi, presents the new ideas that he pioneered. This review provides a good summary.
The earliest studies of networks assumed that they were organized randomly with each node having about the same chance as any other to make a connection to another node. In fact many networks are organized quite differently. They are scale free.
To contrast this compare a highway map of the US to an airline route map. Some cities have more roads and others less, but most have about the same number of roads to and from them. The difference between the largest cities and the smallest isn't thousands or millions. There is an average numbers of roads per city and most cities don't deviate by much from the average. The distribution is a bell curve.
An airline route map shows major hubs, the largest of which have hundreds or thousands of routes, whereas the smallest cities may have only a few flights. The distribution of the number of cities with a given number of links follows a power law, with many cities having few routes and few cities having many routes. The latter has no scale, no reference point like the average number of highways to a city. Power laws ... is a mathematical paper, but the first part has some nice diagrams comparing the graph of male height with that of city population. It also has some nice examples of power-law (scale-free) distributions such as word frequency (Moby Dick words and frequency table).
Social networks exhibit interesting patterns. On the Gallery of network images, check out high-school dating, Les Miserables, Websites, and Books on Politics. Mark Granovetter showed that weak ties, links to acquaintances rather than friends, are more helpful in getting jobs that are strong ties.
The small-world phenomenon is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances, illustrated by the Six Degrees of Kevin Bacon game. From here visit the Oracle of Bacon, the Center of the Hollywood Universe, and the 1000 best centers sites.
The structure of real networks is governed by two principles: growth and preferential attachment. Growth, where nodes and links are continually added, contrasts with a static network where the nodes and links are mostly fixed in advance. Preferential attachment can be describe as the rich get richer. Nodes, when deciding where to link, prefer the nodes that have more links. The scale-free structure that develops has some interesting properties. It is very robust, meaning that random failures will not much affect the overall functioning of the network. But it is also quite vulnerable to terrorists who targest major hubs. See
Scale-Free Networks and Terrorism.
The earliest studies of networks assumed that they were organized randomly with each node having about the same chance as any other to make a connection to another node. In fact many networks are organized quite differently. They are scale free.
To contrast this compare a highway map of the US to an airline route map. Some cities have more roads and others less, but most have about the same number of roads to and from them. The difference between the largest cities and the smallest isn't thousands or millions. There is an average numbers of roads per city and most cities don't deviate by much from the average. The distribution is a bell curve.
An airline route map shows major hubs, the largest of which have hundreds or thousands of routes, whereas the smallest cities may have only a few flights. The distribution of the number of cities with a given number of links follows a power law, with many cities having few routes and few cities having many routes. The latter has no scale, no reference point like the average number of highways to a city. Power laws ... is a mathematical paper, but the first part has some nice diagrams comparing the graph of male height with that of city population. It also has some nice examples of power-law (scale-free) distributions such as word frequency (Moby Dick words and frequency table).
Social networks exhibit interesting patterns. On the Gallery of network images, check out high-school dating, Les Miserables, Websites, and Books on Politics. Mark Granovetter showed that weak ties, links to acquaintances rather than friends, are more helpful in getting jobs that are strong ties.
The small-world phenomenon is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances, illustrated by the Six Degrees of Kevin Bacon game. From here visit the Oracle of Bacon, the Center of the Hollywood Universe, and the 1000 best centers sites.
The structure of real networks is governed by two principles: growth and preferential attachment. Growth, where nodes and links are continually added, contrasts with a static network where the nodes and links are mostly fixed in advance. Preferential attachment can be describe as the rich get richer. Nodes, when deciding where to link, prefer the nodes that have more links. The scale-free structure that develops has some interesting properties. It is very robust, meaning that random failures will not much affect the overall functioning of the network. But it is also quite vulnerable to terrorists who targest major hubs. See
Scale-Free Networks and Terrorism.
Labels: power law, preferential attachment, scale-free
posted by art gittleman at
7:06 AM
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home