Network Analysis and Graph Theory

• Networks and graphs share many similarities, though distinctions appear in some literature
• Networks are applied objects used to study relations among entities and components
• Graphics are abstract mathematical objects for studying topologies over sets

Graph Theory

• Offers a common approach to analyzing networks
• It involves a collection of nodes/vertices and edges that join pairs of nodes

Network Analysis Subproblems

• Centrality analysis identifies prominent nodes
• Community detection identifies groups within the network
• Positional analysis identifies nodes with similar roles
• Dynamic analysis studies network changes and evolution
• Outlier analysis involves space partitioning, classification, and anomaly detection
• Economic analysis covers pathfinding and cost analysis

Basic Definitions

• Graph G is an ordered pair G = (V, E), where V is a set of nodes and E is a subset of V × V, representing unordered pairs of vertices known as edges
• Visualizations dont impact meaning; connections define the graph
• Repeated edges in E are called multi-side, multiple, or parallel edges
• Endpoints of an edge e form the elements of e like (vi, vj); vi and vj are endpoints of e = (vi, vj)
• A link is an edge where vi ≠ vj where endpoints are different nodes
• A loop is where vi = vj where the endpoints are the same

Graph Attributes

• Nodes and edges can have attributes; nodes can be labeled, edges directed or weighted
• Directed Edge: An edge where the ordering matters, also known as an arrow or arc
• Directed Graph: all edges are directed, and E becomes a set of ordered pairs

Weighted Graph

• A graph G = (V, E) with a relation W between an edge and a number set X
• Each edge e ∈ E has an associated numeral value w(e), mathematically represented as ∀e ∈ E: w: e → x with w(e) ∈ W and x ∈ X
• w(e) is the weight of e, and when w(e) < 0, e is a negative edge
• Directed variants can also be made

Multigraph

• Is an ordered pair G = (V, E) where V is a set of nodes and E ⊆ V × V is a multiset of unordered pairs of vertices (edges)
• A multiset contains multiple copies of the same element
• They can have weighted and directed variants

Simple Graph

• Excludes multiple edges or loops
• Different classification types exist based on graph characteristics

Chain

• Defined as a sequence of alternating vertices in V and edges in E, starting and finishing on vertices
• The succession of is known as the chain

Shortest Path

• The (aka. the geodesic) is the path between two nodes that needs to traverse the shortest chain
• In a weighted graph, the sum of the lengths of edges in the chain is the weight, so the shortest path between two nodes is the one with with the least weight among all the possible paths

Types of chains

• A chain is closed if vi = vj+1, else open
• Two nodes are connected if there is a chain/path between them
• Otherwise, they are disconnected
• Two vertices vi, vj ∈ V are adjacent if e = (vi, vj) and e ∈ E, and e is incident on the two vertices vi, vj

Adjacency Matrix

• Edges in a simple graph can be encoded using a matrix
• Denoted as AG(vi, vj), it is a |V| × |V| square matrix symmetric for non-directed graphs (AG(vi, vj) = AG(vj, vi) if the graph is non-directed)

Centrality Analysis

• Aims to identify prominent nodes based on a given measure of importance
• Used for vulnerability analysis, understanding influence and power, or ranking webpages
• Focuses on node centrality, but edge centrality also exists
• Centrality is sometimes used interchangeably between node and edge

Degree Centrality

• Quantifies node importance by counting incident edges, where the number of edges incident on a node v ∈ V is its degree
• Affected by network density, direction, weights, and graph type

In Directed Graphs

• Degree centrality is divided into in-degree and out-degree

In Weighted Graphs

• Calculating degree centrality involves either ignoring weights or using node strength as a proxy

In Multigraphs

• Options include ignoring parallel edges or counting them independently

Betweenness Centrality

• It uses network flows to quantify centrality, with more central nodes sustaining more flows
• Assuming no weights or directions, flows follow shortest paths between nodes
• The betweenness centrality of a node is the number of shortest paths crossing it
• Freeman's betweenness centrality is a common estimator
• Affected by edge directionality and weight; different estimators exist for various graph types

Calculations

• Here are the equations to workout the maximum number of edges in a simple graph
• It you consider a graph where every node is connected to every other - you will have |V|2 edges
• Once we remove all |V| loops that form around a single node, we get the formulas for the maximum number of edges in an undirected (divided by two as we should only have one edge between any two given nodes) and directed graph respectively
• Directed Graph |E | = |V|2 - |V| |E| = |V| * ( |V| - 1)
• Undirected Graph |E| = (|V| * (|V| - 1) )/ 2 and then |E| = |V| * ( |V| - 1)