graph theory

Graph

A collection of vertices and edges

Simple Graph

A graph with no loops and no multiple edges between any two vertices.

Loops

An edge that connects a vertex to itself.

Multiedges

More than one edge between the same pair of vertices.

Degree

The number of edges connected to a vertex.

Directed Graph

A graph where edges have direction, going from one vertex to another.

Weighted Graph

A graph where edges have values (weights) assigned to them.

Order of a Graph

The number of vertices; typically denoted by n.

Size of a Graph

The number of edges; typically denoted by m.

Degree Distribution

A count of how many vertices have each degree.

Connected Graph

A graph where every vertex can reach every other vertex.

Disconnected Graph

A graph that is not fully connected.

Degree Centrality

A measure of how important a vertex is based on how many edges are connected to it

Closeness Centrality

measure of how important a vertex is based on the average distance to all other vertices

Local Clustering Coefficient

Measures how many of a vertex’s neighbors are connected to each other.

Transitivity

Probability that a vertex’s neighbors are also neighbors with each other.

Subgraph

A graph made from a subset of vertices and edges of a larger graph.

Random Variable

A variable whose value is based on a random process.

Range of a Random Variable

The set of all possible values a random variable can take.

Expectation Value

Average of a variable if infinite tests were conducted

Law of Large Numbers

As trials increase, the average result gets closer to the expected value.

Monte Carlo Algorithm

algorithm that determines result using random sampling from large number of experiments

Erdős Rényi Random Graph

A simple graph where each pair of vertices is connected independently with a fixed probability p