一种基于Hadoop平台的社区发现算法

摘要

本发明公开了一种基于Hadoop平台的社区发现算法，在MapReduce架构下实现，包括四个步骤：①读入社会网络数据，构建无向图G，通过数据分片得到节点n、相关节点个数D；②计算每两个节点之间的紧密度，并将处理后的数据写出到文件；③分割数据行为边和紧密度，完成节点集，将数据以（节点，节点集编号）的形式存储在数据结构Hashtable中；④根据步骤三的数据，找出未加入节点集的节点，将其划入与其有联系的相关节点所在节点集中。本发明显著提高了算法的数据处理能力，将运算规模提高到上亿次，大幅提高了对大规模社交网络的挖掘和分析能力，实时性高；本发明基于全网络进行分析和搜索，采用从社区核心向外逐渐扩散的挖掘方式，提高了社区算法的效率，准确度高。

主权项

一种基于Hadoop平台的社区发现算法，其特征在于：所述社区发现算法在hadoop平台的MapReduce架构下实现，包括以下四个步骤：步骤一：读入社会网络数据，根据网络中成员的关系，构建一个相互连接的无向图G，将无向图G中的成员用节点n表示，成员与成员之间的关系用边m表示；在配置有 Hadoop 环境的计算集群上完成数据分片，数据作为Mapper输入；计算得到节点n、以及与每个节点有关联的相关节点个数D，确定系统中最大相关节点个数Dmax，将节点n、相关节点个数D的数据存储在数据结构Hashtable中；步骤二：查询步骤一的Hashtable数据，计算每两个节点之间的紧密度，并将紧密度作为key、边作为value使用Context上下文对象写出，修改Compare方法使数据按倒叙排序；Reduce过程中的key为重写的DoubleWritable，value集合里面只包含一条数据，通过迭代，将数据使用上下文对象写出到一个文件，并再存储一份以边为key、以紧密度为value的Hashtable；步骤三：以步骤二写出的文件所在目录为输入目录，分割数据行为边和紧密度两部分，将当前边以静态字符串形式存储在程序中；任意选择一条边作为第一条边，判断边两端的两个节点是否在节点列表，若在节点列表中，则放入当前节点集，将所有与当前节点集合中节点紧密度最大的节点依次加入节点集，直至符合要求的节点被全部找出，结束添加、完成一个节点集；对节点集进行编号，以节点集编号为key、节点为value的形式使用上下文对象Context写出；Reduce过程以节点集编号作为key、节点为value作为输入，将数据以（节点，节点集编号）的形式存储在数据结构Hashtable中；步骤四：根据步骤三的数据，找出未加入节点集的节点，将其划入与其有联系的相关节点所在节点集中；在Map过程将Hashtable中的社区数据一次性写出；在Reduce过程将Map写出的数据以（节点集编号，节点）的形式写出在HDFS文件上。