Mahout计算大数据量的Local Clustering Coefficient

Clustering Coefficient(聚集系数,简称CC)有两种:一个是Global的定义,用于衡量整个网络的聚集性;还有一种是Local,用于衡量网络中每个节点的聚集特性。这里只讨论怎样计算local CC,即需要计算网络中每个节点的CC。
(为什么图论中有这么多的概念简称都是CC…还有一个CC是connected component)

对于一个无向图来说,节点的local CC计算公式(from Wiki):

C_i = \frac{2|\{e_{jk}\}|}{k_i(k_i-1)} : v_j,v_k \in N_i, e_{jk} \in E.

公式计算了节点i的local CC。其中,k_i是节点i的度数,即节点i的邻居节点数。简单的说,local CC表示的是节点的好友之间互为好友的概率。

基本思路

graph

图中红色的边表示节点和它好友之间的连接,红色边的数量就是节点的度数,这个是比较容易计算的。蓝色的边是好友之间的连接。则上面的公式可以改写成:
CC = 2 * numOfBlueEdge) / ( numOfRedEdge * (numOfRedEdge – 1) )
所以单个节点计算的关键,变成了如何获取蓝色边的数量。

换个角度观察,在上图中,每条蓝边都可以和两条红边一起组成一个三角形(triangle),所以,我们可以通过计算这些三角形的数量来代替蓝边的数量。
当然,这样做似乎更麻烦了。但是,三角形有一个非常重要的特性,即每一个三角形都表示它的每个顶点有一对好友之间有一条边。例如如果存在三角形A-B-C(A,B,C都代表一个节点),则表示A有一对好友之间存在一条边(即B-C这条边),同理可得B和C。
所以,我们可以枚举出整个网络中所有的三角形。对于每个三角形,它的三个顶点的numOfBlueEdge都+1。这样就可以得到所有节点的numOfBlueEdge,然后根据公式即可算得所有节点的local CC。

计算local CC的问题转换成了另一个问题:找到网络中所有的三角形。(三角形对于社会网络分析中其它的问题也很有帮助,比如Community Detection)

Mahout算法

不知道为什么,Mahout将所有用Hadoop实现的graph相关的算法都移除了。给出的理由是MapReduce并不适合用来实现这些Graph相关的算法(确实如此,很多graph的基本算法我用MapReduce实现都可费劲了,而且运行时间也很长)。也许它是希望将来用某个开源的类Pregel来实现吧。

但对于我来说,只有Hadoop这个资源可用。所以我又把那些代码找回来了。

所有和graph相关的代码都放在了package org.apache.mahout.graph下面。和计算local CC有关的主要是这两个:
org.apache.mahout.graph.common.EnumerateTrianglesJob 和
org.apache.mahout.graph.common.LocalClusteringCoefficientJob
其中,
EnumerateTrianglesJob计算得到了整个网络的所有triangle,而LocalClusteringCoefficientJob则根据EnumerateTrianglesJob的结果来计算节点的local CC。
这里重点分析EnumerateTrianglesJob。

EnumerateTrianglesJob一共包含了5次MapReduce Job:

graph

流程:

整个任务的输入是社交关系graph所有的无向边,例如:
Node A — Node B
ScatterJob和JoinJob的工作很简单,就是得到所有边的两个顶点的度数。JoinJob的输出如下:
Node A: degreeOf(A) — Node B: degreeOf(B)

比较关键的是ScatterToLowerJob这一步操作。
它的Mapper会根据边的两个节点度数的大小进行排序,度数小的节点会放在前面,代码如下:

    public static class ScatterEdgesToLowerDegreeVertexMapper extends
            Mapper<UndirectedEdgeWithDegrees, Writable, Vertex, Vertex> {

        @Override
        protected void map(UndirectedEdgeWithDegrees edge, Writable value,
                Context ctx) throws IOException, InterruptedException {
            VertexWithDegree first = edge.getFirstVertexWithDegree();
            VertexWithDegree second = edge.getSecondVertexWithDegree();

            if (first.degree() < second.degree()) {
                ctx.write(first.vertex(), second.vertex());
            } else {
                ctx.write(second.vertex(), first.vertex());
            }
        }
    }

它的Reducer将节点的邻居聚合起来,然后邻居间两两发射一条边missingEdge。相当于将节点的邻居间所有可能的连接遍历。missingEdge的数量就等于前面公式中的numOfRedEdge * (numOfRedEdge – 1) / 2。代码如下:

@Override
protected void reduce(Vertex vertex, Iterable<Vertex> vertices,
        Context ctx) throws IOException, InterruptedException {
    FastIDSet bufferedVertexIDs = new FastIDSet();
    for (Vertex firstVertexOfMissingEdge : vertices) {
        LongPrimitiveIterator bufferedVertexIdsIterator = bufferedVertexIDs
                .iterator();
        while (bufferedVertexIdsIterator.hasNext()) {
            Vertex secondVertexOfMissingEdge = new Vertex(
                    bufferedVertexIdsIterator.nextLong());
            UndirectedEdge missingEdge = new UndirectedEdge(
                    firstVertexOfMissingEdge, secondVertexOfMissingEdge);
            ctx.write(new JoinableUndirectedEdge(missingEdge, false),
                    new VertexOrMarker(vertex));
        }
        bufferedVertexIDs.add(firstVertexOfMissingEdge.id());
    }
}

ScatterToLowerJob得到了邻居间所有可能的边。而PrepareInputJob则将graph重新包装一下,相当于是得到了邻居间实际产生的边。

JoinTriadsJob将所有可能的边与实际产生的边combine到一起,得到所有蓝边的数量,即triangles的数量。

Tips

整个算法的思路其实很简单。唯一比较会让人费解的是,为什么需要事先计算出每条边的两个顶点的度数?在ScatterToLowerJob中,为什么需要按照边两个顶点的度数进行排序,调换顶点的位置?

假设将图表示为G = (V, E),用Γ(v)表示顶点v的邻居的集合:Γ(v) = { w ∈ V | (v, w) ∈ E } ,那么简单的计算图中每个顶点Local CC的算法可以表示为:

simple

这个计算中,每个Triangle会被计算3遍(因为Triangle的每个顶点都会将它计算一次)。

更加糟糕的是,由于社交网络的特性,图中存在着少量的度数极高的中心节点,这些节点的邻居很多,往往也存在着大量的Triangle。如果用MapReduce计算,会导致“curse of last reducer”现象,即当大多数reducer已经计算完成时,少量的reducer为了计算这些中心节点而导致计算时间远远大于其它的reducer,整体任务的计算时间也由于这些reducer而显著变长。

为了解决这两个问题:重复计算了Triangle 和 “curse of last reducer”,对算法做了一些小修改。根据边的顶点的度数调换顶点的位置,让度数小的顶点作为Reducer的Key,这样一方面每个Triangle只会被计算一次,即只在度数最小的那个节点中被计算;另一方面,因为Triangle优先在度数小的节点中计算,度数大的节点需要的计算量显著降低。

Advertisements
相册 | 此条目发表在Large Scale, Mahout分类目录,贴了, 标签。将固定链接加入收藏夹。

One Response to Mahout计算大数据量的Local Clustering Coefficient

  1. Pingback引用通告: [图数据管理和挖掘]笔记 – 上 | Great Power Law

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s