Network Theory Lecture Notes

1. Introduction to Network Theory

Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects. It is a subfield of computer science and graph theory, but it has applications in many disciplines, including physics, biology, economics, and sociology. In computer science, a network is essentially a graph.

A network consists of:

• Nodes (Vertices): The fundamental units of the network. Examples include people in a social network, web pages in the World Wide Web, or neurons in a brain.
• Edges (Links): The connections between the nodes. Examples include friendships on Facebook, hyperlinks between websites, or synapses between neurons.

2. Types of Graphs

When modeling a network, we must define the nature of the connections.

2.1 Undirected vs. Directed

In an undirected graph, edges have no orientation. The relationship is mutual. For example, a friendship network on Facebook is usually undirected (if A is friends with B, B is friends with A).

In a directed graph (or digraph), edges have a direction. The relationship goes from one node to another. For example, Twitter followers are directed; user A can follow user B without user B following back.

2.2 Unweighted vs. Weighted

In an unweighted graph, edges represent only the presence or absence of a connection. The edge is either 1 (exists) or 0 (does not exist).

In a weighted graph, each edge carries a value (weight) representing the strength, capacity, or cost of the connection. For example, in a transportation network, the weight could represent the distance or travel time between two cities.

3. Graph Representation

To analyze networks computationally, we need ways to represent them mathematically and digitally.

3.1 Adjacency Matrix

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

For weighted graphs, the 1 is replaced by the weight of the edge.

3.2 Adjacency List

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This representation is more memory-efficient for sparse graphs (graphs where the number of edges is much less than the possible number of edges).

4. Key Metrics and Concepts

To understand the structure of a network, we calculate specific metrics.

4.1 Degree

The degree of a node is the number of edges connected to it. In a directed graph, we distinguish between in-degree (number of incoming edges) and out-degree (number of outgoing edges).

4.2 Paths and Distance

A path is a sequence of edges which connect a sequence of vertices. The shortest path between two nodes is the path with the fewest edges (or minimum total weight).

The distance between two nodes is the length (number of edges) of the shortest path connecting them. The diameter of a network is the longest shortest path between any pair of nodes in the network.

4.3 Clustering Coefficient

The clustering coefficient measures the degree to which nodes in a graph tend to cluster together. It indicates how connected a node's neighbors are to each other. If the neighbors of a node are also neighbors of each other, the clustering coefficient is high.

Evidence suggests that in most real-world networks (like social networks), nodes tend to create tightly knit groups characterized by a relatively high clustering coefficient.

5. Centrality Measures

Centrality measures identify the most important vertices within a graph. "Importance" can be defined in various ways depending on the context.

5.1 Degree Centrality

Degree centrality is the simplest measure. It is defined as the number of links incident upon a node. A node with high degree centrality is a hub.

5.2 Betweenness Centrality

Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It reflects the amount of control a node has over the flow of information in the network.

5.3 Closeness Centrality

Closeness centrality measures how close a node is to all other nodes in the network. It is calculated as the inverse of the sum of the shortest distances between the node and all other nodes.

A node with high closeness centrality can spread information to the rest of the network very quickly.

5.4 Eigenvector Centrality

Eigenvector centrality assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.

6. Network Models

How do real-world networks form? We use theoretical models to understand their topology.

6.1 Random Networks (ErdsRnyi)

In a random network, edges are placed between nodes with a fixed probability. While simple, random networks often fail to capture the properties of real-world networks, such as clustering and the presence of hubs.

6.2 Small-World Networks (Watts-Strogatz)

The "small-world" phenomenon (six degrees of separation) is modeled here. These networks have high clustering (like regular lattices) but short path lengths (like random graphs). This is achieved by randomly rewiring a few edges in a regular lattice.

6.3 Scale-Free Networks (BarabsiAlbert)

A scale-free network is a network whose degree distribution follows a power law. In these networks, a few nodes (hubs) have a very high degree, while most nodes have a low degree. This emerges from a process of "preferential attachment" (the rich get richer), where new nodes are more likely to connect to existing nodes that already have many connections.

7. Applications of Network Theory

Network theory provides tools to analyze complex systems across various domains:

• Social Network Analysis: Understanding influence, community structures, and information flow.
• Biological Networks: Analyzing protein-protein interaction networks, neural networks, and metabolic pathways.
• Computer Science: Designing robust internet architectures, search algorithms, and cybersecurity protocols.
• Epidemiology: Modeling the spread of diseases through contact networks to predict outbreaks and plan interventions.

8. Conclusion

Network Theory provides a powerful framework for analyzing the interconnected world. By representing systems as graphs, we can utilize mathematical tools to uncover structure, identify key players (nodes), and understand the dynamics of flow and resilience. Whether analyzing social circles, biological ecosystems, or computer infrastructure, the principles of nodes and edges remain fundamental to understanding complexity.