二度人脉算法:广度搜索算法，Hadoop实现

   最近做了一个项目，要求找出二度人脉的一些关系，就好似新浪微博的“你可能感兴趣的人” 中，间接关注推荐；简单描述：即你关注的人中有N个人同时都关注了 XXX 。

     在程序的实现上，其实我们要找的是：若 User1 follow了10个人 ｛User3，User4，User5，... ，User12｝记为集合UF1，那么 UF1中的这些人，他们也有follow的集合，分别是记为： UF3（User3 follow的人），UF4，UF5，...，UF12；而在这些集合肯定会有交集，而由最多集合求交产生的交集，就是我们要找的：感兴趣的人。

     我在网上找了些，关于二度人脉算法的实现，大部分无非是通过广度搜索算法来查找，犹豫深度已经明确了2以内；这个算法其实很简单，第一步找到你关注的人；第二步找到这些人关注的人，最后找出第二步结果中出现频率最高的一个或多个人，即完成。

     但如果有千万级别的用户，那在运算时，就肯定会把这些用户的follow 关系放到内存中，计算的时候依次查找；先说明下我没有明确的诊断对比，这样做的效果一定没 基于hadoop实现的好；只是自己，想用hadoop实现下，最近也在学；若有不足的地方还请指点。

     首先，我的初始数据是文件，每一行为一个follow 关系 ida+‘\t’+idb；表示 ida follow idb。其次，用了2个Map/Reduce任务。

Map/Reduce 1：找出 任意一个用户 的 follow 集合与 被 follow 的集合。如图所示：

代码如下：

     Map任务： 输出时 key ：间接者 A 的ID ，value：follow 的人的ID 或 被follow的人的ID

 public void map(Text key, IntWritable values, Context context) throws IOException,InterruptedException{

        int value = values.get();

        //切分出两个用户id

        String[] _key = Separator.CONNECTORS_Pattern.split(key.toString());

        if(_key.length ==2){

            //"f"前缀表示 follow；"b" 前缀表示 被follow

            context.write(new Text(_key[0]), new Text("f"+_key[1]));

            context.write(new Text(_key[1]), new Text("b"+_key[0]));

        }

    }

　　Reduce任务： 输出时    key ：间接者 A 的ID ， value为 两个String，第一个而follow的所有人（用分割符分割），第二个为 被follow的人（同样分割）

protected void reduce(Text key, Iterable pairs, Context context)

     throws IOException,InterruptedException{

        StringBuilder first_follow = new StringBuilder();

        StringBuilder second_befollow = new StringBuilder();

          

        for(TextPair pair: pairs){

            String id = pair.getFirst().toString();

            String value = pair.getSecond().toString();

            if(id.startsWith("f")){

                first_follow.append(id.substring(1)).append(Separator.TABLE_String);

            } else if(id.startsWith("b")){

                second_befollow.append(id.substring(1)).append(Separator.TABLE_String);

            }

        }

          

        context.write(key, new TextPair(first_follow.toString(),second_befollow.toString()));

    }

　其中Separator.TABLE_String为自定义的分隔符；TextPair为自定义的 Writable 类，让一个key可以对应两个value，且这两个value可区分。

 

Map/Reduce 2：在上一步关系中，若B follow A，而 A follow T ，则可以得出 T 为 B 的二度人脉，且 间接者为A ，于是找出 相同二度人脉的不同间接人。如图所示：

代码如下：

     Map 任务：输出时 key 为 由两个String 记录的ID表示的 二度人脉关系，value 为 这个二度关系产生的间接人的ID

public void map(Text key, TextPair values, Context context) throws IOException,InterruptedException{

        Map first_follow = new HashMap();

        Map second_befollow = new HashMap();

        String _key = key.toString();

        String[] follow = values.getFirst().toString().split(Separator.TABLE_String);

          

        String[] second = values.getSecond().toString().split(Separator.TABLE_String);

          

        for(String sf : follow){

              

            first_follow.put(sf , _key );

              

        }

          

        for(String ss : second){

              

            second_befollow.put(ss , _key );

              

        }

          

        for(Entry f : first_follow.entrySet()){

            for(Entry b : second_befollow.entrySet()){

                context.write(new TextPair(f.getKey() ,b.getKey()), new Text(key));

            }

        }

    }

　Reduce任务：输出时 key 仍然为二度人脉关系， value 为所有间接人 的ID以逗号分割。

protected void reduce(TextPair key, Iterable values, Context context)

    throws IOException, InterruptedException {

      

    StringBuilder resutl = new StringBuilder();

    for (Text text : values){

        resutl.append(text.toString()).append(",");

    }

      

    context.write(key, new Text(resutl.toString()));

}

到这步，二度人脉关系基本已经挖掘出来，后续的处理就很简单了，当然也基于二度人脉挖掘三度，四度：）

付：

广度优先算法（Breadth-First-Search），又称作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索演算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。广度优先搜索的实现一般采用open-closed表。

 1234? ? ? 5? ? ?

 1简介

由图一可以知道，这样形成的一棵树叫搜索树。初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索（DFS——Depth First search）和广度优先搜索（BFS——Breadth First Search）。

2作法

BFS是一种盲目搜寻法，目的是系统地展开并检查中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。

从算法的观点，所有因为展开节点而得到的子节点都会被加进一个的中。一般的实作里，其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中（例如伫列或是），而被检验过的节点则被放置在被称为closed的容器中。（open-closed表）

3实作方法

首先将根节点放入伫列中。从伫列中取出第一个节点，并检验它是否为目标。 如果找到目标，则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入伫列中。若伫列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。重复步骤2。

4特性

空间复杂度 因为所有节点都必须被储存，因此BFS的空间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。注：另一种说法称BFS的空间复杂度为O(B)，其中 B 是最大分支系数，而 M 是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。

时间复杂度

最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。

完全性

广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。

最佳解

若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法成本一致搜寻法（en:uniform-cost search）来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。

5应用

广度优先搜索算法能用来解决图论中的许多问题，例如：

寻找图中所有连接元件（Connected Component）。一个连接元件是图中的最大相连子图。寻找连接元件中的所有节点。寻找非中任两点的最短路径。测试一图是否为。(Reverse) Cuthill–McKee算法

寻找连接元件

由起点开始，执行广度优先搜索算法后所经过的所有节点，即为包含起点的一个连接元件。

测试是否二分图

BFS 可以用以测试二分图。从任一节点开始搜寻，并在搜寻过程中给节点不同的标签。例如，给开始点标签 0，开始点的所有邻居标签 1，开始点所有邻居的邻居标签0……以此类推。若在搜寻过程中，任一节点有跟其相同标签的邻居，则此图就不是二分图。若搜寻结束时这种情形未发生，则此图为一二分图。

应用于电脑游戏中平面网格

BFS 可用来解决电脑游戏（例如即时策略游戏）中找寻路径的问题。在这个应用中，使用平面网格来代替图形，而一个格子即是图中的一个节点。所有节点都与它的邻居（上、下、左、右、左上、右上、左下、右下）相接。

值得一提的是，当这样使用BFS算法时，首先要先检验上、下、左、右的邻居节点，再检验左上、右上、左下、右下的邻居节点。这是因为BFS趋向于先寻找斜向邻居节点，而不是四方的邻居节点，因此找到的路径将不正确。BFS 应该先寻找四方邻居节点，接着才寻找斜向邻居节点1。