Databases Reference
In-Depth Information
b
a
c
e
d
Figure11.13
A graph,
G
, where vertices
c
,
d
, and
e
are peripheral.
Example11.19
Measurements based on geodesic distance.
Consider graph
G
in Figure 11.13. The
eccentricity of
a
is 2, that is,
eccen
.
a
/D 2,
eccen
.
b
/D 2, and
eccen
.
c
/D
eccen
.
d
/D
eccen
/D 3. Thus, the radius of
G
is 2, and the diameter is 3. Note that it is not necessary
that
d
D 2
r
. Vertices
c
,
d
, and
e
are peripheral vertices.
.
e
SimRank:SimilarityBasedonRandomWalk
andStructuralContext
For some applications, geodesic distance may be inappropriate in measuring the simi-
larity 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.
Example11.20
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 net-
work, 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 a message can be passed from Ada to Bob and vice versa. However, this
information is not useful for
AllElectronics'
customer relationship management because
the company typically does not want to send a specific message from one customer to
another. Therefore, geodesic distance does not suit the application.
“What does similarity mean in a social network?”
We consider two ways to define
similarity:
Two customers are considered similar to one another if they have similar neighbors
in the social network. This heuristic is intuitive because, in practice, two people
receiving recommendations from a good number of common friends often make
similar decisions. This kind of similarity is based on the local structure (i.e., the
neighborhoods
) of the vertices, and thus is called
structural context-based similarity
.
