by Kayla Aguilar, Maris James, and Aynsley S.

Data is all around us, but it has to be studied in some way, right? How else are we supposed to know what it’s about? That’s what graph theory and network science are for! To organize and connect data mathematicians use networks and graphs as well as scientific computing (like coding).

Network science is an application-based study of graphs. To understand network science, we first have to understand the graphs:

Graph Theory

Graphs represent data through nodes, which are the separate points of a graph, and edges, which connect the nodes. There are two types of graphs: directed and undirected graphs. Directed graphs rely on the order of the vertices to be the same, while undirected graphs don’t rely on the order of the nodes.

Important Terms for Graph Theory

• Node
  • the units or points on a graph
• Edge
  • lines that connect nodes on a graph
•  Adjacent
  • occurs when two nodes share an edge
  • the order is not important (ex: AB is the same as BA)
• Degree
  • number of edges adjacent to a certain node
• Components
  • parts of an unconnected graph
• Subgraph
  • part of a graph
• Loop
  • an edge that starts and ends at the same node
  • adds two to the node’s degree
• Multi-graph
  • has at least one loop
• Simple graph
  • has no loops

Theorems and Important Statements in Graph Theory

1. The number of edges in a graph (m) is equal to half the sum of the degrees of all the nodes in the graph (n):  m = n/2.
2. Saying that two nodes are “adjacent” is more specific than saying they are “connected”.

Euler Circuits and Paths

In the late 1700s, Leonhard Euler started to question the paths between different nodes and how nodes were connected. He looked at the map of the city of Königsberg, in Prussia, and wondered whether there was a route through which one would cross each of Königsberg’s bridges ONLY ONCE.

Based on his observations, a few terms are defined:

• Euler Circuits
  • occur when a set of edges are connected and begin and end at the same vertex
  • must have NO vertices of odd degree.
• Euler Paths
  • occur when a graph is connected
  • must have two or fewer vertices of odd degree.

Theorems

1. In order for there to be an Euler Path in a graph, that graph must be connected and have 2 or fewer vertices of odd degree.
2. All Euler Circuits are Euler Paths and all circuits are paths, but not all Euler Paths are Euler Circuits, and not all paths are circuits.

Complete and Regular Graphs

A complete graph is a graph in which each node is adjacent to every other node in the graph. The number of edges in any complete graph (m) is equal to the number of nodes (n), times the nodes minus one, divided by two:  m = n × (n – 1)/2. A complete graph can have Euler Circuits if it has an odd number of nodes.

A regular graph is a graph in which each vertex (or node) has the same degree.

It is important to note that regular graphs may not always be complete, but complete graphs are always regular.

Hamilton Circuits and Paths

Other forms of paths and circuits are the Hamilton, or Hamiltonian, paths and circuits.

• Hamilton circuit
  • visits each vertex once
  • starts and ends at the same place.
• Hamilton path
  • visits each vertex once
  • starts and ends at different places.

The number of Hamilton circuits of any complete graph with n nodes is (n – 1)!. This means that the number of Hamilton circuits is:

n – 1! = (read n-1 factorial) =  (n – 1) × (n – 2) × (n – 3) × … × 2 × 1

That is, the factorial of a number (say, n-1!) is defined by starting at the number (here n – 1) and multiplying by one less than the previous term until you reach 1.

Computing In Python

Unlike in the spy movies, coders can’t debug a system or create a program in ten seconds. In fact, coding using Python doesn’t even require ages of classes on advanced coding. All you need to begin is a basic knowledge of simple math and some fingers! The majority of graph theory is inputted by hand, but mathematicians constantly use Python for more complex scenarios and problems.

Python can be used in many different ways, including inputting graphs, drawing graphs, compute the degrees of a graph’s vertices, and how to find the Euler Circuits/Paths in a graph.

Important Variables for Python

• Edgelist
  • the primary list of edges in the graph
• Variable
  • specific case-sensitive name
  • Float
    • real number in Python that can have both an integer and/or an irrational number
  • Integer
    • a number without a fractional part
  • String
    • represents text
  • Boolean
    • represents logical values (True or False)
  • ___.count
    • counts how many times something occurs
  • ___.index
    • counts and organizes variables
  • ___.capitalize
    • capitalizes the first letter of a value
  • ___.replace
    • replaces parts or a whole variable
  • ___.append
    • adds something to the end of the edgelist
  • plt.show
    • displays the graph based on the data given in the program
  • degree distribution
    • some nodes have very high degrees while others have very low degrees

Graph Types in Python

The majority of the graphs found on Python can be referred to as random graphs. These types of graphs are generated from probabilistic calculations. The Erdős–Rényi model, also called ER graphs, is a graph where an unknown amount of edges (m) are randomly placed between an unknown amount of nodes. The Barabasi-Albert model, or a BA model, is a small graph that repeatedly adds 1 node and an unknown amount of edges (k) at each step of the code. The Watts-Strogatz model, or a WS graph, is a graph where most nodes are not neighbors, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a small number of hops or steps.

Community Detection

Community detection is a well-known method for deducing the structure of networks in a community. It is used in many applications in daily life such as finding neurons in the brain, creating social groups on Facebook while finding common interests among people, and even to find ties to frequent offenders of the law. Communities like these can be created in graphs when some nodes have more edges between them than others, so they are grouped together. They then become modular, which means that they have very well defined communities in the graph.

|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|

Can You Solve The Euler Path Problem?

Leonhard Euler developed his theories after trying to figure out a path within a city using bridges. Can you figure it out?

Below we report an attempt at solving the problem, but there are many more ways to solve the puzzle! Use a piece of paper and a pencil, or print out this page. Good luck!

Instructions:
Find a route in the city wherein one would cross each of the seven bridges (labeled a through f) once and only once.

The images featured in this post are from:
https://skymind.com/wiki/graph-analysis
http://social-physics.net/what-is-network-analysis/
https://en.wikipedia.org/wiki/Leonhard_Euler
https://golem.ph.utexas.edu/category/2007/02/this_weeks_finds_in_mathematic_5.html