Introduction to Graph Theory

tags: Social Networks and Group Behaviors

Brief View to Graph and Its Properties

A graph is a way of specifying relationships among a collection of items.A graph consists of a set of objects, called nodes (節點), or sometimes we call it vertx in mathematics, with certain pairs of these objects connected by links called edges (邊). Any finite graph can be geometrically represented by a drawing obtained in the following manner. First, draw a dot for each vertex. Then, for every edge

$e\in E$ with two endpoints, draw a line between the dots representing the vertices of

$V(e)$, and for every edge with only one vertex, draw a line from the dot representing that vertex to that dot itself.

For example, let

$V=\{v_1,v_2,v_3,v_4\}$, and let

$E=\{e_1,e_2,e_3,e_4\}$. Also, let

$V(e_1)=\{v_1{v}_2\}$,

$V(e_2)=\{v_1,v_3\}$,

$V(e_3)=\{v_2,v_3\}$, and

$V(e_4)=\{v_3,v_4\}$.

We say that two nodes are neighbors if they a reconnected by an edge. In many settings, however, we want to express asymmetric relationships ─ for example, that

$A$ points to

$B$ but not vice versa. (a) an undirected graph (無向圖), and (b) a directed graph (有向圖).

The main reason to categorize undirected and directed graph is to analyze how these nodes interact with each other on the graph, by checking their direction, which indicates how messages, diseases, or ideological content are transmitted. In mathematical graph theory, we can convert the graph into a matrix form. For example, given 3 agents, i.e.

$N=\{1,2,3\}$, and if we draw a graph where a link between nodes 1 and 2, a link between nodes 2 and 3, but no link between nodes 1 and 3, the matrix form of this undirected or unweighted network can be represented as:

$$g=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& 0\end{array}\right)$$

Foundations of Graph Theory

Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1736 laid the foundations of graph theory and prefigured the idea of topology.

The problem was to devise a walk through the city that would cross each of those bridges once and only once. By way of specifying the logical task unambiguously, solutions involving either

• reaching an island or mainland bank other than via one of the bridges, or
• accessing any bridge without crossing to its other end
  are explicitly unacceptable.

Euler proved that the problem has no solution. The difficulty he faced was the development of a suitable technique of analysis, and of subsequent tests that established this assertion with mathematical rigor.

Arpanet

The Advanced Research Projects Agency Network (ARPANET) was the first wide-area packet-switched network with distributed control and one of the first networks to implement the TCP/IP protocol suite.

The 13-node Arpanet is an example of a communication network, in which nodes are computers or other devices that can relay messages, and the edges represent direct links along which messages can be transmitted.

Graph Applied in Reality

The application of graph are arising in different domains recently.For instance, (a) and (b) show transportation networks, where the nodes represent destinations, and edges represent direct connections. Much of the terminology surrounding graphs is based on metaphors drawn from transportation through networks of roads, rail lines, or airline flights. In part (c), we see an example of a dependency network, where the nodes represent tasks, and directed edges indicate that one task must be performed before another. The design of complex software systems and industrial processes often requires the analysis of enormous dependency networks, which has significant consequences for efficient scheduling. Finally, in part (d), we see an example of a structural network, which has joints as nodes and physical linkages as edges. The internal frameworks of mechanical structures such as buildings, vehicles, or human bodies are based on such networks, and rigidity theory, which is at the intersection of geometry and mechanical engineering, studies the stability of such structures from a graph-based perspective. These images were sourced from various domains to showcase how graph theory is pervasive in many disciplines.

Path and Connectivity

Walk

A walk (步) in graph theory is like a continuous line that can intersect itself and go forwards or backwards. Specifically, a "walk of length

$n$ from

$u$ to

$v$" in a graph

$G$ is a sequence of vertices and directed edges,

$$W=v_0,e_1^{{\sigma }_1},v_1,e_2^{{\sigma }_2},\cdots ,e_n^{{\sigma }_n},v_n,\mathrm{\forall }{\sigma }_i=+\text{ or }-$$

whose initial vertex

$v_0$ is u, whose final vertex

$v_n$ is

$v$, and for

$i=1,\cdots ,n$, the directed edge

$e_1^{{\sigma }_1}$ runs from the vertex

$v_{i-1}$ to the vertex

$v_i$.

Path

A path (路徑) is a simple graph whose vertices can be ordered so that two vertices are adjacent if and only if they are consecutive in the list. Precisely, an open walk is called a "path" if its vertices are distinct. Thus, a path is the combinatorial analog of a homeomorphic image of a closed line segment. The standard path with

$n$ vertices is called the "

$n$-path" and is denoted

$P_n$. If we want to emphasize that the path we are discussing does not repeat nodes, we can refer to it as a simple path (單向路徑).

Cycle

A closed walk is called a "cycle" (環) if every pair of vertices except its starting and stopping vertex are distinct. Thus, a cycle is the combinatorial counterpart to the homeomorphic image of a circle. The standard cycle with

$n$ vertices is called the "

$n$-cycle" and is denoted

$C_n$. More precisely, a cycle is a path with at least three edges, in which the first and last nodes are the same, but otherwise all nodes are distinct.

More generally, cycles in communication and transportation networks are often present to allow for redundancy (冗餘性); they provide for alternative routes that go the "other way" around the cycle.

Connectivity

Given a graph, it is natural to ask whether every node can reach every other node by a path. With this in mind, we say that a graph is connected if, for every pair of nodes, there is a path between them. The "connectivity" of a graph

$G$ is defined to be the minimum number of points whose removal results in a disconnected graph, a trivial graph, or a bouquet of circles. It may be observed that G has the same connectivity as

$G^{\text{simp}}$.

Precisely, a graph

$G$ is connected if it has a

$u,v$-path whenever

$u,v\in V(G)$ (otherwise,

$G$ is disconnected). If

$G$ has a

$u,v$-path, then

$u$ is connected to

$v$ in

$G$. The connection relation on

$V(G)$ consists of the ordered pairs

$(u,v)$ such that

$u$ is connected to

$v$.

Component

If a graph is not connected, then it breaks apart naturally into a set of connected "pieces", which is called component (成分) —— groups of nodes with the property that each group is connected when considered as a graph in isolation, and no two groups overlap.

The graph in the above figure consists of three such pieces: one consisting of nodes

$A$ and

$B$, one consisting of nodes

$C$,

$D$, and

$E$, and one consisting of the rest of the nodes.

We say that a connected component of a graph is a subset of the nodes such that

• every node in the subset has a path to every other and
• the subset is not part of some larger set with the property that every node can reach every other

There is a useful qualitative way of thinking about the connected components of typical large networks. The global friendship network is not connected due to the brittleness of connectivity. A single node or a small set of nodes can break it. For instance, a person with no friends or a remote island with no outside contact can create isolated components in the network.

Large, complex networks often have what is called a giant component (最大成分), which is a deliberately informal term for a connected component that contains a significant fraction of all nodes.

Distance and Breadth-First Search

Distance

We define distance (距離) between two nodes in a graph to be the length of the shortest path between them, where length measures the number of steps it contains from beginning to end —— in other words, the number of edges in the sequence that comprises it.

Breadth-first Search(BFS)

The breadth-first search algorithm is used to search a tree or graph data structure for a node that meets a set of criteria. It starts at the tree’s root or graph and searches/visits all nodes at the current depth level before moving on to the nodes at the next depth level. Breadth-first search can be used to solve many problems in graph theory. The procedure is shown below.

1. First declare all of your actual friends to be at a distance of 1.
2. Then find all of their friends (not counting people who are already friends of yours), and declare these to be at a distance of 2.
3. Then find all of their friends (again, not counting people whom you’ve already found at distances of 1 and 2) and declare these to be at a distance of 3.

Continuing in this way, search in successive layers, each of which represents the next distance out. Each new layer is built from all those nodes that

• have not already been discovered in earlier layers and
• have an edge to some node in the previous layer.

Following is the example python code for BFS.

from collections import defaultdict
# using adjacency list representation

class Graph:

	# Constructor
	def __init__(self):

		# default dictionary to store graph
		self.graph = defaultdict(list)

	# function to add an edge to graph
	def addEdge(self, u, v):
		self.graph[u].append(v)

	# Function to print a BFS of graph
	def BFS(self, s):
            # Mark all the vertices as not visited
            visited = [False] * (max(self.graph) + 1)

            # Create a queue for BFS
            queue = []

            # Mark the source node as
            # visited and enqueue it
            queue.append(s)
            visited[s] = True

            while queue:

                # Dequeue a vertex from
                # queue and print it
                s = queue.pop(0)
                print(s, end=" ")

                # Get all adjacent vertices of the
                # dequeued vertex s. If a adjacent
                # has not been visited, then mark it
                # visited and enqueue it
                for i in self.graph[s]:
                    if visited[i] == False:
                        queue.append(i)
                        visited[i] = True

# Create a graph given in
# the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Following is Breadth First Traversal"
	  "(starting from vertex 2)")
g.BFS(2)

# This code is contributed by Neelam Yadav

The Small-World Phenomenon

Take the example of a friend who grew up in another country:
following a path through this friend, to his or her parents, and to their friends, you have followed only three steps and ended up in a different part of the world, in a different generation, with people who have very little in common with you.

This idea has been termed the small-world phenomenon (小世界理論) – the idea that the world looks "small" when you think of how short a path of friends it takes to get from you to almost anyone else. It is also known, perhaps more memorably, as the six degrees of separation; this phrase comes from the play of this title by John Guare.