The Internet

About 50 years ago, the US was developing a communication system that would survive a nuclear attack. A centralized command system would be vulnerable as a nuclear attack would handicap all equipment within the range of detonation. Destroying the central node would destroy all forms of communication. A decentralize system would offer the early system of a scale-free network, and the ideal system would be a mesh like network, redundant enough that if some nodes go down, alternative paths would maintain the connections.

Who would have thought that this network described would be like the Internet.



Understanding the topology of the Internet is a prerequisite for designing tools and services that offer a fast and reliable communication infrastructure. Though human made, the Internet is not centrally designed. Structurally, the Internet is closer to an ecosystem than a machine. Understanding the Internet hence would not just be mathematical or an engineering problem; a tangled tale of convergence of a massive scale gave birth to this jumbled information mass for historians and computer scientists to unravel.

It is important to know the Internet topology to design better tools and services. The current Internet protocols were developed with a small network and 1970s technology. As the network grow and new applications emerged, these protocols often fall short of our desires. Today, the Internet is almost exclusively used for the World Wide Web and e-mail. Had the original creators foreseen this, they would have designed a very different infrastructure, resulting in a much smoother experience. Instead we are locked in a technology that adapts only with great difficulty to the booming diversity and demand imposed by the increasingly creative use of the Internet.

Even as biologists unravel the science and codes behind our DNA, neither computer scientists nor sociologists know how this large-scale structure emerged and change until we put the pieces together in this fast evolving system.

--------------------------------------------------------------------------


The Web.

In the early days of the Internet, there were many webpages, and they were only often linked by a webring. But to find things effectively, you would need to find a very connected hub and search for information you need. Then robots started crawling and visiting Webpages, reading and indexing millions of Webpages. This was the beginning of piecing together a fragmented Web, the beginning of the search engine.

The topology of the Web limits our ability to see everything out there. The World Wide Web is a scale-free network, dominated by hubs and nodes with a large number of links, but also coexists with numerous small-scale structures that severely limit how much we can explore simply by clicking our way along the links.

Even with the world's best search engine, there are still many webpages that will not show up due to the Internet's topology. The Web can be best described as fragmented continents with occasional tubes and connections to other continents and islands. There are places you can go on a continent and sometimes going down that path does not lead you back.

The Internet grows faster than ever. Everyday, new pages are created, pictures, videos and other files uploaded. Our life is increasingly dominated by the Web with the explosion of Social Media, and it has pretty much changed our views on privacy and sharing our slice of life with others. It is a revolution in information access, a new way of life that previous generation have not enjoyed. As it continues to evolve, the question is, what do we have to lose in the meantime?

--Robin Low

Transmission of ideas, fads and diseases

As we learn from the previous posts, real networks are scale-free networks, and there is much similarities between different scale free networks, however, by studying some of them, we could model the others.

Before adopting any innovation, we normally ask ourselves several questions: Should I spend time evaluating the new product? Should I spend money on it? How would I know it would work for me as promised? As there were little guarantee that the extra benefits would be worth it, the first adopters still took the risks, and this group are called the innovators.

All of us know some innovators. They are the first ones who buy the Android Phones, and drive the new hybrid cars. They are the teens who pick up on new trends before they become mainstream, the artists and intellectuals who nurture ideas well before they reach the rest of us through books, movies and magazines. If the hubs resist a product, they form such an impedance that even the best innovations fail, however if the hubs accept it, they influence a large number of people. These hubs or -- opinion leaders are nearly changing everything we know regarding the spread of ideas, innovations, and virtues.

Threshold model

To explain the disappearance of some fads and virtues, and the spread of others, the threshold model is developed. The speed at which the likelihood that it will be adopted by a person introduced to it is not the only factor that determine whether or not people will adopt it. There is a threshold -- a critical number of people that is required to adopt it before the innovation spreads, and the number of people adopting it will increase exponentially until everybody who could use it does.

Understanding this phenomena is an important conceptual advance in understanding spreading and diffusions. Epidemiologists work with it when they model the probability that a new infection will run into an epidemic, as the AIDS virus did. Marketing textbooks talk about it when estimating the likelihood a product will make it in the marketplace or understand why some never do. Sociologists use it to explain the spread of birth control practices among women.

This simple paradigm dominated our treatment of diffusion problem. If we wanted to estimate the probability that an innovation would spread, we needed only to know its spreading rate and the critical threshold it faced. Nobody questioned this paradigm, but we have learnt that some viruses and innovations are oblivious to it.

Of the hundred of social links each of us have, only a few are intimate enough to transmit a sexual disease. Therefore AIDS advances on a very sparse subnet of our highly interlinked social web. With the relatively low contagiousness, you should find the epidemic should have died out by now. Despite the odds, however, AIDS has already infected 50 million people, and the numbers continue to rise. To understand the spread of the disease better, one would need a map of the sex web, but this is simply impossible. Hardly anyone would give out the names of everybody with whom they had sex with in the past.

Despite the fact that there are several effective treatments for AIDS, there are still lots of people infected worldwide. The crisis faced by Africa is most severe. The problem is not only that most African countries cannot pay for the drug. Even if they drug prices were to drop, these nations lack the infrastructure to distribute and administer the treatment.

The early spread of AIDS were attributed by mainly homosexual sex, today heterosexual sex is the leading means of transmission. As we've learnt that hubs play a key role in spreading AIDS, as long as resource is finite, we should treat the hubs, before the others, but the problem is often not as simple as many other factors play a role. Doubtless, many hubs will go undiscovered and a few nonhubs will make the list. Furthermore, any selective process will raise an ethical question: "Are we rewarding the promiscuous?" Are we ready to offer drugs to the more connected poor prostitute than to the wealthier but sexually less connected middle class?

Currently, the world spends US$350 million on AIDS vaccine research and more than US$3 billion on AIDS drugs in America and Europe.

Though networks can be modeled after well documented spread of diseases, there are still many unpredictable differences and factors which are hard to model in the real world. The concept is similar and it can help us understand the diffusions through hubs, and know is half the battle won.

-- Robin Low

Networking Fundamentals & Network Modeling

Hub and Connectors

Connectors are an extremely important component of our social network. They create trends and fashions, make important deals, spread fads, or help launch a new business. Connectors are nodes with an anomalously large number of links.

The Internet is the Ultimate freedom of speech. When your views are published, it will be available instantaneously available to anyone around the world with an Internet connection. With the billions of webpages on the web, the question is -- will anybody notice it?

In order to be read, you have to be visible. On the web, the measure of visibility is the number of links. The more incoming links pointing to your webpage, the more visible it is. The average Webpage only has about five to seven links, each pointing to one of the billion pages out there. The likelihood that a typical document is linked to your Webpage is practically zero.

Just as in Society a few connections know an unusually large number of people, and the Internet is dominated by a few highly connected nodes, or hubs. These hubs, such as Yahoo! and Google are extremely visible. In a collective manner, we somehow create hubs, Websites to which everyone links. Compared to these hubs, everyone is invisible. Some pages linked to one or two documents do not exist and even search engines are biased against them, ignoring them as they crawl the web looking for the hottest new sites.

Hubs dominate the structure of all networks which they are present, making them look like small worlds. With unusually large number of links to large number of nodes, hubs create short paths between any two nodes in the system. From the perspective of the hub, the world is tiny. (For Google, reaching webpages are often two to three clicks away)

The 80/20 Rule

Pareto's Law or principle, known also as the 80/20 rule, has been turned into the Murphy's Law of management: 80 percent of profits are produced by 20 percent of the employees, 80 percent of the problems are produced by 20 percent of the consumers, 80 percent of the decisions are made during 20 percent of the meeting time, and so on. Similarly, we can use it to describe the phenomenon that 80 percent of the links connect to 20 percent of the Webpages.

The Rich get Richer

The initial network model start on two simple and often disregarded assumptions; the number of nodes is fixed and remain unchanged throughout the network's life, all nodes are equivalent. With the discovery of hubs, and the power laws that describe them, we need to abandon these assumptions.

On the World Wide Web, even for searches on Google with the keyword "news", there are 100,000,000 hits. How do we pick one? The random network models tell us to select randomly, however no one ever does this. Without giving much thought we may pick BBC.com or CNN.com and unconsciously, we prefer to link hubs. The better known they are, the links point to them. The more links they attract, the easier it is to find them on the Web as we are more familiar with them. We all have this unconscious bias, linking with higher probability to the nodes we know, which are inevitably the more connected nodes of the Web. We prefer hubs.

Preferential attachment rules in many different networks. In Hollywood, the producer whose job is to make the movie profitable know that stars sell movies. Thus casting is determined by two competing factors: the match between the actor and the role, and the actor's popularity. The more movie the actor has made, the higher the probability he gets casted by the producer.

Winner Takes All

Nodes compete for connections because links represent survival in an interconnected world. In most cases, this competition is overt, as when companies compete for consumers, actors strive for opportunities to perform, people vie for social links. In a winner takes all scenario, competition leads to a scale free topology. Most real networks belong to this category, and the winner shares the spotlight with continuous hierarchy of hubs. Networks are competitive systems that fight fiercely for links. Like it or not, we are all part of a complex competitive game.

.... To be Continued

-- Robin Low