Introduction to Network Thinking in Computer Science

INTRODUCTION TO NETWORK THINKING

Let start from the title of the course-> «Network thinking and Agent-based modeling» What is «network thinking»? Network thinking means focusing on relationships between entities rather than the entities themselves.

Network thinking has recently helped to illuminate additional, seemingly unrelated, scientific and technological mysteries:

• Why is the typical life span of organisms a simple function of their size?
• Why do rumors, jokes, and "urban myths" spread so quickly?
• Why are large, complex networks such as electrical power grids and the Internet so robust in some circumstances and so susceptible to large-scale failures in others?
• What types of events can cause a once-stable ecological community to fall apart?
• How can the dynamics of diffusion of knowledge be rationalized?

The Impact of Network Science

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?

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)
• Links to the connections between them (e.g., synapses, Web hyperlinks, social relationships).

Xiao Kim Gar Melanie David Greg Steph Doug Karen Seth Ginger Sid Bob Doyne Charlie John Sander Scott Jacques FIGURE 15.2. Part of my own social network.

The Common Jargon of Networks

• 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.
• 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.
• High-degree nodes are called hubs; they are major conduits for the flow of activity or information in networks.

Degree Distribution Example

Why Skewed Degree Distribution?

A major discovery to date of network science is that high clustering, skewed degree distributions, and hub structure seem to be characteristic of the vast majority of all the natural, social, and technological networks that network 6 5 Number of Nodes 4 3 2 1 0 1 2 3 4 5 6 7 8 9 10 Degree FIGURE 15.3. The degree distribution of the network in figure 15.2. For each degree, a bar is drawn representing the number of nodes with that degree.scientists have studied.

Why do networks in the real world have these characteristics? This is a major question of network science, and has been addressed largely by developing models of networks. Two classes of models that have been studied in depth are known as small- world networks and scale-free networks.

A Real Network Example

• The dots (or nodes) represent cities
• the lines (or links) represent flights between cities.

Small World Networks

To determine the degree of "smallworldness" in a network, Watts and Strogatz computed the average path length in the network. The path length between two nodes is simply the number of links on the shortest path between those two nodes.

"only a few random links can generate a very large effect . . . on average, the first five random rewirings reduce the average path length of the network by one-half, regardless of the size of the network."

The small-world property: a network has this property if it has relatively few long-distance connections but has a small average path-length relative to the total number of nodes.

A Paramount Example of Network Science Relevance

• WEB SEARCHES: search engines worked by simply looking up the words in your search query in an index that connected each possible English word to a list of Web pages that contained that word.
• PAGE RANK: " The idea was that the importance (and probable relevance) of a Web page is a function of how many other pages link to it (the number of "in-links")

The Web as a Scale-Free Network

If we look at the WWWeb as a network, with nodes being Web pages and links being hyperlinks from one Web page to another, we can see that PageRank works only because this network has a particular structure: as in typical social networks, there are many pages with low degree (relatively few in-links), and a much smaller number of high-degree pages (i.e., relatively many in-links).

Web In-degree Distribution

Web's in-degree distribution can be described by a very simple rule: The number of pages with a given in-degree is approximately proportional to 1 divided by the square of that in-degree: (n(ID=x)=1/(ID=x)2) The distribution is called self-similar, because it has the same shape at any scale you plot it. In more technical terms, it is "invariant under rescaling." 2This is what is meant by the term scale-free.

Power-law and Scale-free Networks

Scale-free network = power-law degree distribution. A very important property of scale-free networks is their resilience to the deletion of nodes: This means that if a set of random nodes (along with their links) are deleted from a large scale-free network, the network's basic properties do not change:

• It still will have a heterogeneous degree distribution, short average path length, and strong clustering
• This resilience comes at a price: if one or more of the hubs is deleted, the network will be likely to lose all its scale-free properties and cease to function properly

Examples of Networks: The Brain

Why the Brain is a Network

The brain can be viewed as a network at several different levels of description; for example, with neurons as nodes and synapses as links, or with entire functional areas as nodes and larger- scale connections between them (i.e., groups of neural connections) as links.

The brain has small-world properties. Neuroscientists have mapped the connectivity structure in certain higher-level functional brain areas in animals such as cats, macaque monkeys, and even humans and have found the small- world properties in those structures.

Resilience might be one major reason: we know that individual neurons die all the time, but happily, the brain continues to function as normal. Researchers have hypothesized that a scale-free degree distribution allows an optimal compromise between two modes of brain behavior: processing in local, segregated areas such as parts of the visual cortex or language areas versus global processing of information, for example, when information from the visual cortex is communicated to areas doing language processing, and vice versa.

Evolution presumably selected more energy-efficient structures. The brain would probably have to be much larger to fit all those connections. At the other extreme, if there were no long-distance links in the brain, it would take too long for the different areas to communicate with one another.

Examples of Networks: Epidemiology

Epidemiologists studying sexually transmitted diseases often look at networks of sexual contacts, in which nodes are people and links represent sexual partnerships between two people. The resulting network has a scale-free structure. the vulnerability of such networks to the removal of hubs can work in our favor. 3How can these hubs be identified without having to map out huge networks of people, for which data on sexual partners may not be available?

A clever yet simple method was proposed by another group of network scientists:

• choose a set of random people from the at-risk population and ask each to name a partner.
• Then vaccinate that partner.
• People with many partners will be more likely to be named, and thus vaccinated, under this scheme.

This strategy, of course, can be exported to other situations in which "hub- targeting" is desired

Examples of Networks: Ecologies and Food Webs

The common notion of food chain has been extended to food web, a network in which a node represents a species or group of species; Applying network science to the analysis of these webs in order to understand biodiversity and the implications of different types of disruptions to that biodiversity in ecosystems.

Several ecologists have claimed that (at least some) food webs possess the small-world property and that some of these have scale-free degree distributions, which evolved presumably to give food webs resilience to the random deletion of species.

Why Scale-Free Networks?

In 1999 physicists Albert-László Barabási and Réka Albert proposed that a particular growing process for networks, which they called preferential attachment, is the explanation for the existence of most (if not all) scale-free networks in the real world:

• The idea is that networks grow in such a way that nodes with higher degree receive more new links than nodes with lower degree.
• The rich get richer, or perhaps the linked get more linked. Barabasi and Albert showed that growth by preferential attachment leads to scale-free degree distributions

Malcolm Gladwell defined: the tipping points:

• points at which some process, such as citation, spread of fads, and so on, starts increasing dramatically in a positive-feedback cycle.
• Alternatively, tipping points can refer to failures in a system that induce an accelerating systemwide spread of additional failures.

There is a debate though:

• Even for networks that are actually scale-free, there are many possible causes for power law degree distributions in networks;
• Preferential attachment is not necessarily the one that actually occurs in nature: As Cosma Shalizi succinctly said: "There turn out to be nine and sixty ways of constructing power laws, and every single one of them is right."

Static and Dynamic Aspects of Networks

The structure of networks-e.g., their static degree distributions-is different from the dynamics of spreading information in a network. 4The term information to capture any kind of communication among nodes. Some examples of information spreading are the spread of rumors, gossip, fads, opinions, epidemics (in which the communication between people is via germs), electrical currents, Internet packets, neurotransmitters, calories (in the case of food webs), vote counts, and a more general network-spreading phenomenon called "cascading failure."

Cascade Failures

The phenomenon of cascading failure emphasizes the need to understand how information spreads and how it is affected by network structure .- > A massive power outage Cascading failures provide another example of "tipping points," in which small events can trigger accelerating feedback, causing a minor problem to balloon into a major disruption.

Scaling Relationships

This power law relation is now called Kleiber's law. Such 3/4-power scaling. The larger a mammal is, the longer its life span. The life span for a mouse is typically two years or so; for a pig it is more like ten years, and for an elephant it is over fifty years .- > There are some exceptions to this general rule.

Complexity

Complexity, once an ordinary noun describing objects with many interconnected parts, now designates a scientific field with many branches. A tropical rainforest provides a prime example of a complex system.

At the outset, it is helpful to distinguish complex from complicated-> complicated problems can be hard to solve, but they are addressable with rules and recipes, like the algorithms that place ads on your Twitter feed. They also can be resolved with systems and processes, like the hierarchical structure that most companies use to command and control employees Complex problems involve too many unknowns and too many interrelated factors to reduce to rules and processes.

A technological disruption like blockchain is a complex problem. A competitor with an innovative business model - an Uber or an Airbnb - is a complex problem. There's no algorithm that will tell you how to respond.

Better yet, emergence ('the whole is more than the sum of the parts') helps distinguish complex systems from other systems. Historically, complexity became an increasingly important topic as physicists became intrigued with emergent properties of aggregates of identical elements, such as the 'wetness' of an aggregate of water molecules. There is no reasonable way to assign 'wetness' to individual molecules; wetness is an emergent property of the aggregate. In this, wetness differs from a property like weight, where the weight of the aggregate is simply the sum of the weights of the component parts. 5