Data Mining_ Concepts and Techniques - Jiawei Han [317]
■ “How can we measure the similarity between two objects on a graph accordingly?” Typically, we cannot use conventional distance measures, such as Euclidean distance. Instead, we need to develop new measures to quantify the similarity. Such measures often are not metric, and thus raise new challenges regarding the development of efficient clustering methods. Similarity measures for graphs are discussed in Section 11.3.2.
■ “How can we design clustering models and methods that are effective on graph and network data?” Graph and network data are often complicated, carrying topological structures that are more sophisticated than traditional cluster analysis applications. Many graph data sets are large, such as the web graph containing at least tens of billions of web pages in the publicly indexable Web. Graphs can also be sparse where, on average, a vertex is connected to only a small number of other vertices in the graph. To discover accurate and useful knowledge hidden deep in the data, a good clustering method has to accommodate these factors. Clustering methods for graph and network data are introduced in Section 11.3.3.
11.3.2. Similarity Measures
“How can we measure the similarity or distance between two vertices in a graph?” In our discussion, we examine two types of measures: geodesic distance and distance based on random walk.
Geodesic Distance
A simple measure of the distance between two vertices in a graph is the shortest path between the vertices. Formally, the geodesic distance between two vertices is the length in terms of the number of edges of the shortest path between the vertices. For two vertices that are not connected in a graph, the geodesic distance is defined as infinite.
Using geodesic distance, we can define several other useful measurements for graph analysis and clustering. Given a graph , where V is the set of vertices and E is the set of edges, we define the following:
■ For a vertext , the eccentricity of v, denoted , is the largest geodesic distance between v and any other vertex . The eccentricity of v captures how far away v is from its remotest vertex in the graph.
■ The radius of graph G is the minimum eccentricity of all vertices. That is,
(11.27)
The radius captures the distance between the “most central point” and the “farthest border” of the graph.
■ The diameter of graph G is the maximum eccentricity of all vertices. That is,
(11.28)
The diameter represents the largest distance between any pair of vertices.
■ A peripheral vertex is a vertex that achieves the diameter.
Measurements based on geodesic distance
Consider graph G in Figure 11.13. The eccentricity of a is 2, that is, , , and . Thus, the radius of G is 2, and the diameter is 3. Note that it is not necessary that . Vertices c, d, and e are peripheral vertices.
Figure 11.13 A graph, G, where vertices c, d, and e are peripheral.
SimRank: Similarity Based on Random Walk and Structural Context
For some applications, geodesic distance may be inappropriate in measuring the similarity between vertices in a graph. Here we introduce SimRank, a similarity measure based on random walk and on the structural context of the graph. In mathematics, a random walk is a trajectory that consists of taking successive random steps.
Similarity between people in a social network
Let's consider measuring the similarity between two vertices in the AllElectronics customer social network of Example 11.18. Here, similarity can be explained as the closeness between two participants in the network, that is, how close two people are in terms of the relationship represented by the social network.
“How well can the geodesic distance measure similarity and closeness in such a network?” Suppose Ada and Bob are two customers in the network, and the network is undirected. The geodesic distance (i.e., the length of the shortest path between Ada and Bob) is the shortest path that