Given a node u, the adjacency list of u is a list of all nodes
that u is connected to. If the graph is directed, the list contains
either all the nodes connecting to u, or all the nodes receiving edges
from u, but not both.
Defined in: Adjacency Lists.
The adjacency matrix of a graph with \(n\) nodes is an \(n \times n\) matrix
whose element at the \(i\)-th row and \(j\)-th column indicates whether nodes
i and j are adjacent or not.
Defined in: Adjacency Matrix.
If two nodes u and v are connected by an edge, they are called
adjacent or neighbors. If u and v are adjacent, we write u ~
v.
Defined in: Nodes and Edges. See also: Degree.
It's the average of all local clustering coefficients.
Defined in: Clustering Coeficient. See also: Global Clustering Coefficient.
The average path length is the average distance between every pair of nodes in a graph.
Defined in: Path Lengths. See also: Distance, Diameter.
The Barabási-Albert Random Graph is a model for generating scale-free networks. It depends on two parameters, \(N\), the final number of nodes, and \(m\), the new number of links at each time step. Starting with \(m\) nodes all joined to each other, at each time step we add a new node until there are a total of \(N\) nodes. The links of each new node are formed by choosing among the old ones in proportion to their degree. The probability of a new node linking to an older node with degree \(k\) is
Defined in: Barabási-Albert random graph.
Clustering refers to the extent to which nodes in a network are tightly-knit.
Defined in: Clustering Coeficient.
A complete graph is a graph that has all possible edges present, i.e., its density is equal to \(1\).
Defined in: Graph Density. See also: Density.
A connected component, or simply component, is a set of nodes in which any two are connected by a path. A graph that only has one component is called connected graph
Defined in: Paths and Components. See also: Walk, Cycle, Path.
If three nodes u, v, and w have at least two edges among them, they
are called a connected triad.
Defined in: Triangles and Transitivity. See also: Triangle.
A cycle is a walk whose starting and ending nodes are the same. It is also called a closed walk.
Defined in: Paths and Components. See also: Walk, Path, Connected Component.
The number of edges connecting to a node u is called the degree of
u.
Defined in: Nodes and Edges. See also: Adjacent or Neighbors.
The density of a network is the the number of edges present in the network divided by the total number of possible edges.
Defined in: Graph Density. See also: Complete graph.
The diameter of a graph is the maximum distance between any pair of nodes.
Defined in: Path Lengths. See also: Distance, Average Path Length.
A graph is directed when the edges represent an asymmetric
relationship. In this case, every edge is represented by an oredered pair
of nodes: (u, v), with the first one sometimes being called the source
and the second, the target.
Defined in: Directed Graphs. See also: Undirected graph.
A directed path is an ordered set of nodes (u₁, u₂, ..., uₙ) in
which every consecutive pair uᵢ, uᵢ₊₁ are such that there is an
edge from uᵢ to uᵢ₊₁. If there is a directed path from u to
v, we say v is reachable from u.
Defined in: Paths and Components. See also: Strongly Connected Component.
In graph-theoretical terms, the distance between two nodes is the length of the shortest path joining them. If there is no such path, the distance is \(\infty\). The distance from a node to itself is zero.
Defined in: Path Lengths. See also: Average Path Length, Diameter.
The Erdos-Renyi Random Graph refers to the process of fixing the number of nodes \(n\) and the individual edge probability, \(p\), and drawing one edge at a time, with probability \(p\). Because it depends on two parameters, it is sometimes denoted \(G(n, p)\). This random graph model is so common in Network Science that it is often referred to as just random graph.
Defined in: Erdos-Renyi Random Graph.
Often written as just \(C\), it is defined by the following ratio.
Defined in: Clustering Coeficient. See also: Average Clustering Coefficient.
A graph is defined as a set of nodes, defining the locations, entities or elements of the graph, and a set of edges, representing the relationships between two nodes. Nodes are also called vertices, and edges are sometimes called links.
Defined in: Nodes and Edges. See also: Graph Theory.
A graph measure is a number that describes the network and helps us uncover its underlying structure.
Defined in: Graph Measures.
The field of mathematics concerned with the study of graphs is called graph theory. Network Science relies heavily on graph theory, as every network is represented by a graph.
Defined in: Nodes and Edges. See also: Graph.
A node is called a hub when it holds a considerable proportion of the links in a network. There is no clear-cut definition to call a node a hub.
Defined in: Barabási-Albert random graph.
The incidence matrix of a graph with \(n\) nodes and \(m\) edges is an
\(n \times m\) matrix whose rows represent nodes and whose columns represent
edges. The entry in the \(i\)-th row and \(j\)-th column indicates whether edge
j is incident to node i.
Defined in: Incidence Matrix.
An edge is incident to a node if the node is at one of the edge's endpoints.
Defined in: Incidence Matrix.
The number of incoming edges to u is the indgree of u.
Defined in: Directed Graphs. See also: Outdegree.
The local clustering coefficient of node u, denoted \(c_u\), is defined
by the ratio
Defined in: Clustering Coeficient.
A graph that is not a simple graph is called multigraph.
Defined in: Simple Graphs. See also: Simple graph, Self-loop.
Network transitivity measures the extent to which u ~ v and v ~ w
imply u ~ w.
Defined in: Triangles and Transitivity.
For a given node i, its strength is the sum of the weights of all
edges that connect to i.
Defined in: Weighted Graphs.
For a given node u, the number of outgoing edges from u is called
outdegree of u.
Defined in: Directed Graphs. See also: Indegree.
A path is a walk in which every node is unique. This means the walk
does not loop around into itself: it does not self-cross. If there exists
a path from u to v, we say u and v are connected.
Defined in: Paths and Components. See also: Walk, Cycle, Connected Component.
A function is said to follow a power law when it is (approximately) proportional to a power of its argument,
Defined in: Barabási-Albert random graph. See also: Scale Free Network.
Preferential Attachment is the phenomenon by which a node in a network is more likely to connect to a high degree node.
Defined in: Barabási-Albert random graph.
A random graph is a graph that was generated by some stochastic process. In Mathematics, the term random graph is also used to refer to the ensemble of all such graphs that could possibly be generated by a random process. That is, the process itself embodies the random graph, instead of just one realization of such process.
Defined in: Erdos-Renyi Random Graph.
A network is called scale-free if its degree distribution follows a power-law,
Defined in: Barabási-Albert random graph. See also: Power Law.
An edge that has the same node as both endpoints is called a self-loop.
Defined in: Simple Graphs. See also: Simple graph, Multigraph.
A simple graph is a graph whose edges never join the same node and any pair of nodes is joined by at most one edge.
Defined in: Simple Graphs. See also: Self-loop, Multigraph.
In a directed graph, a strongly connected component is a subset of nodes in which every node is reachable from all the others.
Defined in: Paths and Components. See also: Directed Path.
The matrix \(A\) is symmetric when \(a_{ij} = a_{ji}\) for every possible value of \(i\) and \(j\).
Defined in: Adjacency Matrix.
A triangle in a graph is a triad of nodes where each one is connected to the other two. Every triangle is a connected triad.
Defined in: Triangles and Transitivity. See also: Connected triad.
A graph is undirected when the relationship between nodes is
symmetrical. In this case, every edge is written as an unordered pair of
nodes: {u, v}.
Defined in: Directed Graphs. See also: Directed graph.
A walk is an ordered sequence of nodes (u₁, u₂, ..., uₙ) where
every consecutive pair of nodes are adjacent. That is, each can be reached
from the previous one by following an edge in the graph.
Defined in: Paths and Components. See also: Cycle, Path, Connected Component.
A graph \(G\) is a weighted graph when there is a real number associated to each of its edges. If nodes \(i\) and \(j\) are connected by an edge, then its weight is denoted by \(w_{ij}\).
Defined in: Weighted Graphs.