Skip to content

Graph theory

Graph theory is the branch of mathematics concerned with graphs—abstract representations of systems as sets of vertices (nodes) and edges (connections). A graph is defined by its vertices and edges; variants include:

  • Directed vs. undirected: In directed graphs, edges have a direction (e.g., Twitter follows). In undirected graphs, edges are symmetric (e.g., Facebook friendships).
  • Weighted vs. unweighted: Edges may carry weights representing strength, distance, or cost.
  • Bipartite graphs: Vertices fall into two types, with edges only between types (e.g., users and documents).
  • Hypergraphs: Edges can connect more than two vertices, modeling higher-order interactions.

Foundational concepts

Degree: The number of edges incident to a vertex. In directed graphs, in-degree and out-degree are distinguished.

Paths and distances: A path is a sequence of edges connecting two vertices; the geodesic distance is the shortest path.

Clustering coefficient: Measures whether neighbors of a vertex are themselves connected (triangles in the graph).

Centrality measures: Various metrics quantify the importance or influence of a vertex: degree centrality, betweenness, closeness, eigenvector centrality.

Connected components: Maximal sets of vertices where any two are reachable by a path.

Relevance to networks and misinformation

Graph theory provides the mathematical language for modeling and analyzing networks. Network-based fake news detection often uses graph properties (clustering, shortest paths, centrality) to characterize misinformation campaigns, bot networks, or information cascades.

Key papers