18
Chapter 3. Background
for a pair of vertices to be connected by both a positively and negatively weighted
edge.
Adjacency matrix: An adjacency matrix is one in which each row and column
corresponds to a vertex of a graph, and the element a i j of the matrix is the weight of
the edge connecting node i to node j. For an undirected graph, the adjacency matrix
is necessarily symmetric (A = A ); for a directed graph, it need not be. For a simple
graph, the diagonal of the adjacency matrix is necessarily zero.
Degree: The degree of a node is the number of edges, or the sum of the weights of
the edges, that connect to that node in an undirected graph.
In-degree: For directed graphs, the in-degree of a node is the number of edges, or
sum of the weights of the edges, that end at the node.
Out-degree: For directed graphs, the out-degree of a node is the number of edges,
or sum of weights of the edges, that start at the vertex.
Path: A path from node v i to node v j is a sequence of consecutive edges that start at
v i and end at v j ; the length of the path is the number of these edges, for an unweighted
graph, or the total edge weight along these edges, for a weighted graph.
Geodesic distance: The geodesic distance between vertices v i and v j is the shortest
(weighted) path between them.
Bipartite graph (or bigraph): A bipartite graph is one in which the nodes can be
divided into two disjoint sets so that there is no edge between the nodes in each set.
In other words, all edges connect nodes from different sets.
Clique: A clique is a subset of nodes of an undirected graph in which every pair of
distinct nodes are connected.
Ego network: The ego network of a particular node is the subgraph of which it is
the center. It consists of the node, all of its immediate neighbors, and all of the edges
among them.
Connected graph: A graph is connected when there is a path between any pair
of nodes. The graph representing a large social network may not necessarily be
connected. The set of subgraphs, each of which is connected, are called the connected components of the graph. Often, the graph of a social network contains one
connected component that contains almost all of the nodes, with a few other small
components.
3.2 Spectral graph theory
Spectral graph algorithms are based on eigendecompositions of matrices derived
from adjacency matrices. Conventionally, a matrix is regarded as an operator, but
its eigendecomposition can also be understood as providing insight in the properties
of the matrix as data, and this is the reason for the usefulness of eigendecompositions,
principal component analysis, and matrix decompositions as tools in knowledge discovery [85].
For example, one way to understand an eigendecomposition of a matrix is that
it determines a basis with respect to which the matrix can be expressed in diagonal
form (where the diagonal entries are the eigenvalues).
From another perspective, an eigendecomposition represents a transformation
Chapter 3. Background
for a pair of vertices to be connected by both a positively and negatively weighted
edge.
Adjacency matrix: An adjacency matrix is one in which each row and column
corresponds to a vertex of a graph, and the element a i j of the matrix is the weight of
the edge connecting node i to node j. For an undirected graph, the adjacency matrix
is necessarily symmetric (A = A ); for a directed graph, it need not be. For a simple
graph, the diagonal of the adjacency matrix is necessarily zero.
Degree: The degree of a node is the number of edges, or the sum of the weights of
the edges, that connect to that node in an undirected graph.
In-degree: For directed graphs, the in-degree of a node is the number of edges, or
sum of the weights of the edges, that end at the node.
Out-degree: For directed graphs, the out-degree of a node is the number of edges,
or sum of weights of the edges, that start at the vertex.
Path: A path from node v i to node v j is a sequence of consecutive edges that start at
v i and end at v j ; the length of the path is the number of these edges, for an unweighted
graph, or the total edge weight along these edges, for a weighted graph.
Geodesic distance: The geodesic distance between vertices v i and v j is the shortest
(weighted) path between them.
Bipartite graph (or bigraph): A bipartite graph is one in which the nodes can be
divided into two disjoint sets so that there is no edge between the nodes in each set.
In other words, all edges connect nodes from different sets.
Clique: A clique is a subset of nodes of an undirected graph in which every pair of
distinct nodes are connected.
Ego network: The ego network of a particular node is the subgraph of which it is
the center. It consists of the node, all of its immediate neighbors, and all of the edges
among them.
Connected graph: A graph is connected when there is a path between any pair
of nodes. The graph representing a large social network may not necessarily be
connected. The set of subgraphs, each of which is connected, are called the connected components of the graph. Often, the graph of a social network contains one
connected component that contains almost all of the nodes, with a few other small
components.
3.2 Spectral graph theory
Spectral graph algorithms are based on eigendecompositions of matrices derived
from adjacency matrices. Conventionally, a matrix is regarded as an operator, but
its eigendecomposition can also be understood as providing insight in the properties
of the matrix as data, and this is the reason for the usefulness of eigendecompositions,
principal component analysis, and matrix decompositions as tools in knowledge discovery [85].
For example, one way to understand an eigendecomposition of a matrix is that
it determines a basis with respect to which the matrix can be expressed in diagonal
form (where the diagonal entries are the eigenvalues).
From another perspective, an eigendecomposition represents a transformation