Complexity_ A Guided Tour - Melanie Mitchell [111]
Disparate as these questions are, network researchers believe that the answers reflect commonalities among networks in many different disciplines. The goals of network science are to tease out these commonalities and use them to characterize different networks in a common language. Network scientists also want to understand how networks in nature came to be and how they change over time.
The scientific understanding of networks could have a large impact not only on our understanding of many natural and social systems, but also on our ability to engineer and effectively use complex networks, ranging from better Web search and Internet routing to controlling the spread of diseases, the effectiveness of organized crime, and the ecological damage resulting from human actions.
What Is a ‘Network,’ Anyway?
In order to investigate networks scientifically, we have to define precisely what we mean by network. In simplest terms, a network is a collection of nodes connected by links. Nodes correspond to the individuals in a network (e.g., neurons, Web sites, people) and links to the connections between them (e.g., synapses, Web hyperlinks, social relationships).
For illustration, figure 15.2 shows part of my own social network—some of my close friends, some of their close friends, et cetera, with a total of 19 nodes. (Of course most “real” networks would be considerably larger.)
At first glance, this network looks like a tangled mess. However, if you look more closely, you will see some structure to this mess. There are some mutually connected clusters—not surprisingly, some of my friends are also friends with one another. For example, David, Greg, Doug, and Bob are all connected to one another, as are Steph, Ginger, and Doyne, with myself as a bridge between the two groups. Even knowing little about my history you might guess that these two “communities” of friends are associated with different interests of mine or with different periods in my life. (Both are true.)
FIGURE 15.2. Part of my own social network.
You also might notice that there are some people with lots of friends (e.g., myself, Doyne, David, Doug, Greg) and some people with only one friend (e.g., Kim, Jacques, Xiao). Here this is due only to the incompleteness of this network, but in most large social networks there will always be some people with many friends and some people with few.
In their efforts to develop a common language, network scientists have coined terminology for these different kinds of network structures. The existence of largely separate tight-knit communities in networks is termed clustering. The number of links coming into (or out of) a node is called the degree of that node. For example, my degree is 10, and is the highest of all the nodes; Kim’s degree is 1 and is tied with five others for the lowest. Using this terminology, we can say that the network has a small number of high-degree nodes, and a larger number of low-degree ones.
This can be seen clearly in figure 15.3, where I plot the degree distribution of this network. For each degree from 1 to 10 the plot gives the number of nodes that have that degree. For example, there are six nodes with degree 1 (first bar) and one node with degree 10 (last bar).
This plot makes it explicit that there are many nodes with low degree and few nodes with high degree. In social networks, this corresponds to the fact that there are a lot of people with a relatively small number of friends, and a much smaller group of very popular people. Similarly, there are a small number of very popular Web sites (i.e., ones to which many other sites link), such as Google, with more than