424
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
✦Use of Gradient Descent: If we know membership in communities, we can
ﬁnd the MLE by gradient descent or other methods. However, we cannot
ﬁnd the best membership in communities by gradient descent, because
membership is discrete, not continuous.
✦Improved Community Modeling by Strength of Membership: We can for-
mulate the problem of ﬁnding the MLE of communities in a social graph
by assuming individuals have a strength of membership in each commu-
nity, possibly 0 if they are not a member. If we deﬁne the probability of an
edge between two nodes to be a function of their membership strengths in
their common communities, we can turn the problem of ﬁnding the MLE
into a continuous problem and solve it using gradient descent.
✦Simrank: One way to measure the similarity of nodes in a graph with
several types of nodes is to start a random walker at one node and allow
it to wander, with a ﬁxed probability of restarting at the same node. The
distribution of where the walker can be expected to be is a good measure
of the similarity of nodes to the starting node.
This process must be
repeated with each node as the starting node if we are to get all-pairs
similarity.
✦Triangles in Social Networks: The number of triangles per node is an
important measure of the closeness of a community and often reﬂects its
maturity. We can enumerate or count the triangles in a graph with m
edges in O(m3/2) time, but no more eﬃcient algorithm exists in general.
✦Triangle Finding by MapReduce: We can ﬁnd triangles in a single round
of MapReduce by treating it as a three-way join. Each edge must be sent
to a number of reducers proportional to the cube root of the total number
of reducers, and the total computation time spent at all the reducers is
proportional to the time of the serial algorithm for triangle ﬁnding.
✦Neighborhoods: The neighborhood of radius d for a node v in a directed
or undirected graph is the set of nodes reachable from v along paths of
length at most d. The neighborhood proﬁle of a node is the sequence of
neighborhood sizes for all distances from 1 upwards. The diameter of a
connected graph is the smallest d for which the neighborhood of radius d
for any starting node includes the entire graph.
✦Transitive Closure: A node v can reach node u if u is in the neighborhood
of v for some radius. The transitive closure of a graph is the set of pairs
of nodes (v, u) such that v can reach u.
✦Computing Transitive Closure: Since the transitive closure can have a
number of facts equal to the square of the number of nodes of a graph, it
is infeasible to compute transitive closure directly for large graphs. One
approach is to ﬁnd strongly connected components of the graph and col-
lapse them each to a single node before computing the transitive closure.
