基于GraphX的社区发现-TAOBAO技术部数据挖掘与计算复杂算法

基于GraphX的社区发现淘宝技术部数据挖掘与计算复杂算法复杂网络节点表⽰系统中的个体边表⽰个体之间的关系引言Spark户外活动……-技术讲座-猎头公司-云服务-打折机票-酒店住宿-旅游攻略社区发现CommunityDetection相关工作FastUnfolding算法基于GraphX实现总结相关工作-算法调研GNAlgorithmGN算法[1]每次选择betweenness最大的边进行删除当节点数量较大时，计算全局的betweenness很复杂，可以考虑抽样的方法[2][1]communitystructureinsocialandbiologicalnetworks[2]FastApproximationofBetweennessCentralitythroughSampling相关工作-算法调研LabelPropagationAlgorithm每个点会把它的标签传播到它的邻居，达到稳定后属于同一个标签的点划分到一个社区[3]COPRA[4],每个节点记录多个label，删去概率低于阈值的labelSLPA[5]，不删去label，最后统计各label的频率，去除低频率的label[3]Nearlineartimealgorithmtodetectcommunitystructuresinlarge-scalenetworks[4]Findingoverlappingcommunitiesinnetworksbylabelpropagation[5]TowardsLinearTimeOverlappingCommunityDetectioninSocialNetworks相关工作-算法调研其他算法KCoreSubgraph[6]LocalExpansion[7]ParticleCompetition[8]GameTheory[9]…[6]AcceleratingCommunityDetectionbyUsingK-coreSubgraphs[7]OverlappingCommunityDetectionUsingSeedSetExpansion[8]UncoveringOverlapCommunityStructureinComplexNetworksusingParticleCompetition[9]Agame-theoreticframeworktoidentifyoverlappingcommunitiesinsocialnetworks相关工作-评估标准Q=12𝑚[𝐴𝑖𝑗−𝑘𝑖𝑘𝑗2𝑚]𝑖,𝑗𝛿𝑐𝑖,𝑐𝑗计算公式[10]如下：模块化Modularityijkjki2mAij衡量与随机模型（NullModel）的差异节点i到节点j存在连线可能性[10]Modularityandcommunitystructureinnetworks与j相连总边数为kj总边数为2m与i相连共ki条边实际i与j间边数为AijFastUnfolding算法（Louvain算法）算法流程[11]1.初始化，将每个节点划分在不同的社区中2.对每个节点，计算Modularity增益3.执行Unfolding，合并节点[11]FastalgorithmfordetectingcommunitystructureinnetworksFastUnfolding算法（Louvain算法）算法流程1.初始化，将每个节点划分在不同的社区中2.对每个节点，计算Modularity增益3.执行Unfolding，合并节点FastUnfolding算法（Louvain算法）算法流程1.初始化，将每个节点划分在不同的社区中2.对每个节点，计算Modularity增益3.执行Unfolding，合并节点4.构造新图基于GraphX实现串行化实现对于细粒度的操作，支持并不良好不能充分利用分布式框架高并发、集群计算优势基于分布式图计算框架GraphX？基于GraphX实现并行化实现逐个选择节点改变社区同时改变所有节点的社区基于GraphX实现并行化实现1.获得邻居信息（MapReduceTriplets）Map：生成邻居节点的消息VertexDataReduce：获得所有邻居节点的信息，Id,Array[VertexData]2.获得每个节点新社区Id,getBestCommunity([Array[VertexData]])3.更新图信息，合并节点，进行多轮迭代-步骤VertexDataVertexDataArray[VertexData]基于GraphX实现并行化实现1.使用aggregateMessages替代MapReduceTriplets耗时减少约30%2.使用Kryo进行序列化序列化的耗时减少约5倍，存储空间也有压缩-优化基于GraphX实现并行化实现Modularity中间计算量过大消息滞后-问题基于GraphX实现并行化实现-问题1Modularity中间计算量过大Q=12𝑚[𝐴𝑖𝑗−𝑘𝑖𝑘𝑗2𝑚]𝑖,𝑗𝛿𝑐𝑖,𝑐𝑗pairwiseijkli’j’k’l’基于GraphX实现并行化实现-问题1Modularity中间计算量过大Q=12𝑚[𝐴𝑖𝑗−𝑘𝑖𝑘𝑗2𝑚]𝑖,𝑗𝛿𝑐𝑖,𝑐𝑗pairwiseQ=[in2𝑚−tot2𝑚2𝑐𝑖]其中，in表示一个社区内部的连线数，tot表示一个社区所有点的度数之和。-解决选择合适的模型基于GraphX实现并行化实现-问题2消息滞后社区归属延迟互换社区1243G2G2G1G11243G1G1G2G21243G2G1G3G4123G2G3G3t轮根据t-1轮信息更新12基于GraphX实现并行化实现-问题2消息滞后社区归属延迟互换社区1243G2G2G1G11243G1G1G2G21243G2G1G3G4123G2G3G3t轮根据t-1轮信息更新12-解决12431243尝试使用随机值，即每次会有部分节点的社区保持不变结果不能保证基于GraphX实现并行化实现-问题2消息滞后1243G2G2G1G11243G2G1G3G4-解决以Id,Community构图，再求解连通域IdCommunity12213241srcdst1221324113G1G1基于图的特性基于GraphX实现效果zachary数据集基于GraphX实现效果浏览日志二跳子图总结思考选择合适的模型很重要从图的特性去考虑解决问题结合SparkGraphX的特性求解特点基于Modularity优化的方式Unfolding过程减少节点数加入我们我们需要：—图算法工程师—Spark开发工程师微博：来往：