In 1736, a Swiss mathematician pondered routes for a sightseeing trip along the Pregel River in Königsberg. In 1880, an Italian painter turned zoologist sought to settle a hotly-contested controversy: whether or not birds protect crops by reducing insect populations. In 1932, the superintendent of a girls' reformatory school in Hudson, New York, hired a sociologist to investigate the cause of a recent wave of runaways. In 1955, a U.S. Army General and a mathematician developed a technique for identifying bottlenecks in the Soviet railway system. And, in 1998, two mathematicians in Ithaca, New York tried to figure out (among other things) why exactly all movie stars seem to be connected by Kevin Bacon.

These puzzles, taking place at different times and different places, might, at first glance, appear unrelated. But they have one thing in common: they all revolve around relationships – between people, between places, or between species – and they were all solved using the science of relationships, which has come to be known as network science. Interest in network science has grown considerably in recent years, as online social network platforms, such as Facebook, Twitter, WeChat, and Mastodon, have become increasingly popular.

This book covers the fundamental concepts of network science, as well as how to put them into practice using the Python-based NetworkX package. Part I (Chapter 1, What is a Network?, to Chapter 4, Affiliation Networks) introduces the concept of a network, as well as how to build, manipulate, and visualize networks in NetworkX. Part II (Chapter 5, The Small Scale – Nodes and Centrality, to Chapter 7, In-Between – Communities) demonstrates how to analyze network structure at various scales. Part III (Chapter 8, Social Networks and Going Viral, to Chapter 11, Visualization) applies network science to understanding complex systems using modeling, simulation, and visualization. In this introductory chapter, you'll learn some of the history of network science and the differences between common types of networks. You'll also see examples of different ways that relationships in a network can be interpreted. Finally, you'll get to build and visualize your first network using NetworkX!

In this chapter, we will cover the following topics:

• Network science: Learn the history of the study of networks.
• What is a network?: Understand the fundamental concepts of network science.
• What is NetworkX?: Getting familiar with the NetworkX Python package.
• Types of networks: Meet common variants of networks, and understand their applications.
• Your first network in NetworkX: Try a simple example.

The origins of network science trace back to many different fields. For the most part, researchers in these fields developed the tools and methods of network science without much knowledge of how it was being applied in other fields. It may seem astonishing that scientists working independently in very different fields could develop tools and techniques similar enough to now be considered a single field.

How did this happen? The answer lies in one insight: sometimes, it is useful to study the relationships between things without worrying about the specifics of what those things are. Network scientists didn't study networks for their own sake* – they studied networks in order to better understand people, animal species, atoms, and so on. (* Except for mathematicians. We like to think about weird abstract concepts such as networks just for fun.)

When the specifics of the people/species/atoms being studied were abstracted away, seemingly different problems suddenly became very similar. And that's the power of network science; it provides a general language to talk about relationships and connections, allowing discoveries about one thing to be translated into useful information about many other types of things.

The earliest work recognizable as network science came from the branch of mathematics known as graph theory. Graph theory originated with Leonhard Euler's 1736 solution (Euler, 1953) to the seven bridges problem. At the time, the city of Königsberg, Prussia (now Kaliningrad, Russia) had seven bridges connecting the banks of the Pregel River to two islands (pictured as follows). It was not known whether it was possible to find a path through the city that crossed every bridge exactly once. Euler showed that it was impossible, and he did so using new methods that became the basis for graph theory, and later for network science.

The study of networks also has a rich history in sociology. The sociologists, Jacob L. Moreno and Helen Hall Jennings proposed tools for the quantitative study of interpersonal relationships, which they called sociometry (Moreno & Jennings, 1934). These tools included the sociogram, a graphical representation of social networks very similar to the type of network diagrams currently in use.

When Moreno was hired by Fannie French Morse, superintendent of the New York Training School for Girls, to investigate a wave of runaways, it was sociograms that allowed him to visualize and communicate the nature of the social forces driving the runaways. Many of the tools used in modern network science—centrality, affiliation networks, community detection, and others—come from sociology. Over the past several decades, sociometry has branched into social network analysis, a rich and active subfield within network science.

Various other fields have found it useful to study network structure, and have shared their tools and findings with each other as part of the interdisciplinary complex systems community. Ecologists study food webs—relationships between predator and prey species. Biologists study networks of interactions between genes. Physicists study magnetic interactions between neighboring atoms in crystals. All of these fields are doing exciting work with network science.

And then, of course, there's the internet. The internet itself is literally a network—computers and routers connected to each other by copper wire, fiber optic cables, and so on. But, on top of that, the content on the internet is also networked. Links between web pages form networks, and online social networks allow people to interact by friending or following each other. The Google search engine was founded on the PageRank algorithm (Page et al., 1999), a network-science-based approach to identifying popular websites. Online social networks typically make money by selling advertising space, and using network science to show ads to the people most likely to click on them. If you see a picture of a cute cat online, you can use network science to understand how the picture got to your computer screen, how the picture connects you with your friends, and what the picture tells you about other sites you might like to visit.

With its interdisciplinary nature, network science draws practitioners from a wide variety of backgrounds. At the time of writing this book, only a handful of universities offer programs dedicated to network science, so network scientists tend to be self-taught, or trained as sociologists, physicists, ecologists, and so on. My own path to network science was similarly convoluted. Once an aspiring physicist, I came to realize I cared more about people than atoms, and left grad school to work on technology for civic organizing. When I eventually came across network science, I was excited to find that it was a powerful tool for understanding group behavior, and that the skills I'd learned from physics transferred directly to network science. Since then, I have been using network science to better understand how groups can organize and collaborate more effectively. Whatever your background, network science is a place where everyone fits in because no one fits in.

Network science has experienced rapid growth in recent years, in part due to the popularity of online social networks, digital trace data, and tools such as NetworkX. Once scattered across many different fields, universities are now creating research centers and Ph.D. programs specifically dedicated to network science. Companies have rushed to hire data scientists, including network scientists. There has never been a better time to explore the delightful world of network data.

If you walk down into the Kendall Square subway station in Cambridge, Massachusetts, through the turnstiles and past the Paul Matisse art installation, you will see a common feature of all subways: a map.

If you have ever used a subway map, you know that they are not quite like other maps, which tend to be concerned with details like distance and terrain. Subway maps leave all that out, showing you the bare minimum you need to know to get from one place to another: which stations are connected to each other.

When you're using a subway, it doesn't matter how long a stretch of track is, what exact direction it goes in, or even whether it is above ground, underground, or under water. All you have to do is get on at one station and get off at another, possibly with some transfers between the two. Such a map is an excellent example of the types of networks used by network scientists.

In network science, a network is simply a set of things and the connections between them. The things are called nodes, and the connections are called edges. Nodes are really just placeholders for any type of thing that can have a connection or relationship, such as subway stations, people, or atoms. Similarly, edges are placeholders for connections or relationships, such as subway tracks, friendships, or molecular bonds. Just like the subway map, representing a system as a network strips away a lot of information, making it possible to focus just on the structure.

Networks are often visualized by drawing a dot or circle for each node and a line for each edge, as in the following diagram:

Looking at the network in this diagram, you might as yourself where to draw the nodes. The answer is wherever you want! (Although technically possible, it might be advisable to avoid hot surfaces, the mouths of large predatory animals, and/or important historical documents.) Because networks are meant to focus on structure and connectivity, there are many ways to draw the same network. Nodes can be drawn anywhere. Edges can be straight or squiggly, long or short. Edges can even cross, but that should never be interpreted as being connected to each other!

The same network can be drawn in many other ways, as shown in the following diagram. The nodes have been labelled with letters to make it easier to compare between different network diagrams. Regardless of which diagram you look at, any particular node will be connected to the same set of other nodes. While different ways of drawing the same network are equally correct, some may be helpful at highlighting particular features of the network. Chapter 11, Visualization, describes common approaches to visualizing networks and their various applications:

Remember NetworkX? This is a book about NetworkX. NetworkX is a Python package for modeling, analyzing, and visualizing networks. It provides classes to represent several types of networks and implementations of many of the algorithms used in network science. NetworkX is relatively easy to install and use, and has much of the functionality built-in, so it is ideal for learning network science and performing analyses on small or medium sized networks. There is excellent documentation available on the project website at https://networkx.github.io/.

At the time of writing, NetworkX is in version 2.3. While many things are exactly the same between 1.x versions and 2.x, some basic functionality has changed, so documentation and books relating to older versions may no longer be accurate. This book assumes versions at or above 2.3, so all examples here should work with recent versions of NetworkX.

NetworkX is Free and Open Source Software (FOSS). That means that the source code is available to read, modify, and redistribute (under certain conditions). The code itself is available at https://github.com/networkx/networkx. In addition to the original authors and project maintainers, NetworkX has been written by a community of dozens of contributors. If you have an idea for a new feature or a way to improve the software, you can write it yourself and contribute it back to the community.

The networks presented in this chapter so far have just the bare essentials. These networks are called simple networks because, well, they are simple. In NetworkX, simple networks are represented by the Graph class, described in detail in Chapter 2, Working with Networks in NetworkX.

Sometimes, it helps to add just a little more detail to a network. The edges we've seen so far don't have any sense of coming from or going to; they are simply connections between two nodes, so they are called symmetric or undirected.

Imagine a network that represents a system of roads (edges) and intersections (nodes). A network with undirected edges would be a good representation, until you came across a one-way street. An undirected edge suggests that you can travel in either direction equally well, while in reality, driving against traffic is likely to be a rather different experience from driving with it.

When direction matters, a network is called directed. In a directed network, each edge has a source node and a target node. Typically, the edge represents a flow of some kind, for example, traffic, from the source to the target. But what if not all connections are one-way? Easy! Two-way connections are made by combining two directed edges going in opposite directions. In directed networks, edges are drawn with arrows pointing toward the target, as shown in the following diagram. In NetworkX, directed networks are represented by the DiGraph class, also described in Chapter 2, Working with Networks in NetworkX:

Returning to the case of undirected networks, sometimes, not all edges are created equal. For example, in a network representing a city's water distribution system, the edges could represent a series of tubes that carry the water from one place to another. Some of these might have greater capacity than others. When edges can have different strengths, the network is called weighted, and the strength is quantified by a number called the weight. Both directed and undirected networks can be weighted. An example of a weighted network is shown in the following diagram. When visualizing a network, edge weights are often indicated by varying the thickness or opacity of the edge. Edge weights can be used to represent many different types of attributes. The most common ones are described in the next section:

Edges represent the connections and relationships that make a network. The edges and their weights can have different interpretations, depending on what the network represents. Some common interpretations include the following:

• Friendships
• Flows
• Similarity
• Distance

In social networks, edges most often represent friendship or other interpersonal relationships. Edge weights then represent the strength of the friendship, for example, time spent together, messages exchanged, or the number of common interests.

Flow networks describe the movement of something (people, information, fluid, and so on) from place to place. Edge weights might represent capacity—the maximum amount that can be transported between two nodes—or the actual amount that has traveled through/across the connection.

In similarity networks, connections are less literal and more abstract. Edge weights correspond to how similar two nodes are, often with zero being not at all, and one being identical. For example, one type of similarity between different people could be calculated by taking their top-10 favorite online cat videos and using the fraction of videos that appear for both people. In this case, the edge weight doesn't have anything to do with whether two people have any kind of relationship. It's quite possible to have an edge with a very high weight connecting two individuals who have never even met!

Edges can also represent distance (or closeness), especially when nodes represent locations in space. When using edge weights to represent distance, the distance of an entire trip can be calculated by adding together all of the edge weights along a path. Using edge weights to represent distance can sometimes be confusing because a larger number means a weaker connection, and non-existent edges are actually edges with an infinite weight. Sometimes, it can be more intuitive to use a measure of closeness, such as the reciprocal of the distance, although that can complicate working with paths across many edges.

The previous examples cover many of the common applications of networks, but they are by no means exhaustive. Whenever a group of things can have any type of relationship or connection with each other, it is possible to capture the structure of those connections using a network.

Now, let's create and visualize a small network using NetworkX! For the code in this book, you will need Python 3.4 or higher and NetworkX 2.2 or greater. I also highly recommend Jupyter Lab as an interactive Python environment. The code in this book is available as Jupyter notebooks at https://github.com/PacktPublishing/Network-Science-with-Python-and-NetworkX-Quick-Start-Guide.

The following example creates an undirected, unweighted network, adds edges and nodes, and then generates a visualization. Other types of networks will be discussed in Chapter 2, Working with Networks in NetworkX. First, we import the networkx package. In this book, I will use the convention of importing the library with the alias nx:

import networkx as nx

Next, we create a Graph object, representing an undirected network, given as follows:

G = nx.Graph()

Now that the graph exists, we can add nodes one at a time with the add_node() method, or all at once with add_nodes_from(). When adding nodes to a network, each node has to have a unique ID. The ID can be a number, a string, or a tuple. In fact, you can use any Python object as an ID, as long as it has a __hash__() method defined. For this example, we'll use letters as node IDs, shown as follows:

G.add_node('A')
G.add_nodes_from(['B', 'C'])

Similarly, edges can be added one at a time with add_edge(), or all at once with add_edges_from(), shown as follows:

G.add_edge('A', 'B')
G.add_edges_from([('B', 'C'), ('A', 'C')])

So far, the A, B, and C nodes, as well as the edges connecting them, have been added. The following code draws a simple visualization of the network:

plt.figure(figsize=(7.5, 7.5))
nx.draw_networkx(G)
plt.show()

In the preceding code, figure() is used to create a 7.5 by 7.5 inch figure, which will hold the visualization. The draw_networkx() function uses the Graph object G to produce a visualization. The show() function renders the visualization, but can be omitted if you are running the examples in Jupyter Lab. The visualization should appear similar to the following:

Your visualization may look slightly different from the one shown previously. This is because visualizations in NetworkX sometimes use randomized algorithms. The randomized algorithms can be configured to produce the same output each time by setting the random seed. The following code sets the random seeds used by NetworkX (this code will also appear at the beginning of the example code for all future chapters):

import random
from numpy import random as nprand
seed = hash("Network Science in Python") % 2**32
nprand.seed(seed)
random.seed(seed)

Nodes can also be added using a nifty shortcut. If you try to add an edge referring to a node ID that isn't in the network, NetworkX will automatically add the node! So, in practice, you won't often need to call add_node() directly. The following code adds nodes and edges so that the network matches the example network from earlier and creates a new visualization:

G.add_edges_from([('B', 'D'), ('C', 'E')]) 
nx.draw_networkx(G)

The draw_networkx() function now produces a visualization including the new D and E nodes:

From the bridges of 17^th century Königsberg to the internet, network science emerged from a diverse range of fields, all seeking to quantify and study relationships of some kind. The networks in network science model relationships as edges between nodes, which can represent anything from a species of flower, to an atom in a crystal, to an individual in a society. To quantify properties of relationships, edges can be directed and/or weighted. NetworkX provides Python classes and functions to create and manipulate such networks with ease. By now, you should have a sense of the types of problems network science and NetworkX can solve. The following chapters will cover various applications of network science as well as related features of NetworkX, with examples of how they can be applied to real datasets.

The following is a list of resources that you can consider to get further knowledge:

• Cohen, R., & Ruths, D. (2013). Classifying political orientation on Twitter: It's not easy!. In Seventh International AAAI Conference on Weblogs and Social Media.
• Euler, L. (1953). Leonhard Euler and the Königsberg bridges. Scientific American, 189(1).
• Jernigan, C., & Mistree, B. F. (2009). Gaydar: Facebook friendships expose sexual orientation. First Monday, 14(10).
• Moreno, J. L., & Jennings, H. H. (1934). Who Shall Survive? Nervous and Mental Disease.
• Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.
• Zhang, Y., & Pennacchiotti, M. (2013, May). Predicting purchase behaviors from social media. In Proceedings of the 22nd international conference on World Wide Web. ACM.