计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2013年
1期
221-223
,共3页
社区发现%重叠社区%相似度%划分密度
社區髮現%重疊社區%相似度%劃分密度
사구발현%중첩사구%상사도%화분밀도
针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN.算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区.EGN算法首先需要构造网络节点之间连边关系的边图；然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法；再按照相似度由小到大对边图删除边,构建出边图的树状图.树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分.最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区.
針對GN算法在髮現重疊社區時存在的不足,以及為瞭降低算法時間複雜度,提齣一種基于網絡圖中連邊相似度劃分連邊集的重疊社區髮現算法EGN.算法依據網絡圖的連邊集進行劃分,每一條邊被劃分到某箇特定的社區,而一箇節點可以關聯多條連邊,因此節點可以被劃分到不同的社區,從而髮現重疊社區.EGN算法首先需要構造網絡節點之間連邊關繫的邊圖；然後根據邊圖中節點的關繫計算網絡圖中連邊的相似度,在節點之間相似度的基礎上提齣瞭連邊之間相似度的計算方法；再按照相似度由小到大對邊圖刪除邊,構建齣邊圖的樹狀圖.樹狀圖的每一層對應網絡的一箇劃分,採用劃分密度函數來衡量劃分的質量,以此尋找最優的劃分.最後將算法應用到Zachary空手道俱樂部網絡中,併與GN算法進行對比,實驗結果錶明EGN算法能夠很好地髮現重疊社區.
침대GN산법재발현중첩사구시존재적불족,이급위료강저산법시간복잡도,제출일충기우망락도중련변상사도화분련변집적중첩사구발현산법EGN.산법의거망락도적련변집진행화분,매일조변피화분도모개특정적사구,이일개절점가이관련다조련변,인차절점가이피화분도불동적사구,종이발현중첩사구.EGN산법수선수요구조망락절점지간련변관계적변도；연후근거변도중절점적관계계산망락도중련변적상사도,재절점지간상사도적기출상제출료련변지간상사도적계산방법；재안조상사도유소도대대변도산제변,구건출변도적수상도.수상도적매일층대응망락적일개화분,채용화분밀도함수래형량화분적질량,이차심조최우적화분.최후장산법응용도Zachary공수도구악부망락중,병여GN산법진행대비,실험결과표명EGN산법능구흔호지발현중첩사구.
