Data Mining by Mehmed Kantardzic (good book recommendations TXT) 📕

… , nk} and a set of links between pairs of nodes L = {l1, l2,…, lm}. A graph with nodes and without links is called an empty graph, while the graph with only one node is a trivial graph. Two nodes ni and nj are adjacent if there is a link between them. A graph G(N, L) can be presented as a diagram as in Figure 12.2a in which points depict nodes, and lines between two points are links. A graph G′(N′, L′) is a subgraph of G(N, L) if N′ ⊆ N and L′ ⊆ L.

Figure 12.2. Undirected, directed, and weighted graphs.

An induced subgraph of a graph G has a subset of the nodes of G, and the same links between pairs of nodes as in G. For example, the subgraph (b) in Figure 12.3 is an induced subgraph of the graph (a), but the subgraph (c) is a general subgraph but not an induced subgraph of G, since the incoming link L1 of the node labeled N2 in (a) is not retained in (c) while the node labeled N2 is included.

Figure 12.3. An induced subgraph and a general graph.

The degree of a node, denoted by d(ni), is the number of links connected to the given node. Equivalently, the degree of a node is the number of nodes adjacent to it. For example, in Figure 12.2a the degree d(B) = 3. The degree of a node ranges from a minimum of 0 if no nodes are adjacent to a given node, and to a maximum of k − 1 if a given node is adjacent to all the other nodes in the graph. The degrees are very easy to compute, and yet they can be very informative for many applications. For some applications, it is useful to summarize the degrees of all nodes in the graph. The mean nodal degree is a statistic that reports the average degree of the nodes in the graph:

For the graph in Figure 12.2a, dav = (1 + 3 + 2 + 2)/4 = 2. One might also be interested in the variability of the nodal degrees. If all the degrees of all nodes are equal, the graph is said to be d-regular, and its variability is equal to 0. If the nodes differ in degrees, the variance is calculated as a measure for variability:

The maximum number of links in the graph is defined by the number of nodes. Since there are k nodes in the graph, and if we exclude the loops as links, there are k(k − 1)/2 possible links that could be presented in the graph. If all links are present, then all nodes are adjacent, and the graph is said to be complete. Consider now what proportion of these links is actually present. The density of a graph is the proportion of actual links in the graph compared with the maximum possible number of links. The density of a graph goes from 0, when there are no links in a graph, to 1, when all possible links are presented.

We can also analyze the paths between a pair of nodes, and they are represented by multiple links. We define a path from s ∈ N to t ∈ N as an alternating sequence of nodes and links, beginning with node s and ending with node t, such that each link connects its preceding with its succeeding node. It is likely that there are several paths between a given pair of nodes, and that these paths are differ in lengths (number of links included in the path). The shortest path between two nodes is referred to as a geodesic. The geodesic distance dG or simply the distance between two nodes is defined as the length of a geodesic between them, and it represents the length of the shortest path. By definition, dG(s; s) = 0 for every node s ∈ N, and dG(s; t) = dG(t; s) for each pair of nodes s, t ∈ V. For example, the paths between nodes A and D in Figure 12.2a are A-B-D and A-B-C-D. The shortest one is A-B-D, and therefore the distance d(A,D) = 2. If there is no path between two nodes, then the distance is infinite (or undefined). The diameter of a connected graph is the length of the largest geodesic between any pairs of nodes. It represents the largest nodal eccentricity. The diameter of a graph can range from 1, if the graph is complete, to a maximum of k − 1. If a graph is not connected, its diameter is infinite. For the graph in Figure 12.2a the diameter is 2.

These basic definitions are introduced for non-labeled and nondirected graphs such as the one in Figure 12.2a. A directed graph, or digraph G(N, L) consists of a set of nodes N and a set of directed links L. Each link is defined by an order pair of nodes (sender, receiver). Since each link is directed, there are k(k − 1) possible links in the graph. A labeled graph is a graph in which each link carries some value. Therefore, a labeled graph G consists of three sets of information: G(N,L,V), where the new component V = {v1, v2, … , vt} is a set of values attached to links. An example of a directed graph is given in Figure 12.2b, while the graph in Figure 12.2c is a labeled graph. Different applications use different types of graphs in modeling linked data. In this chapter the primary focus is on undirected and unlabeled graphs although the reader still has to be aware that there are numerous graph-mining algorithms for directed and/or labeled graphs.

Besides a graphical representation, each graph may be presented in the form of the incidence matrix I(G) where nodes are indexing rows and links are indexing columns. The matrix entry in the position (i,j) has value a if node ni is incident with a, the link lj. The other