CAJ | 학술논문

当前社区发现算法主要是针对无向图研究社区结构，但在实际复杂网络中，链接关系时常表现出非对称性或方向性，比如Twitter的用户关注关系，文献网络的引用关系，网页之间的超链接关系等应用网络。因此，本文依据信息在复杂网络中的传播规律和流动方向性，提出了k‐Path共社区邻近相似性概念及计算方法，用于衡量结点在同一社区的相似性程度，并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法（Local and wave‐like extension algorithm of detecting overlapping community ，LWS‐OCD）。在真实数据集上的实验表明，共社区邻近相似性概念实现了有向到无向的合理转换，而且提高了社区结点的聚集效果，LWS‐OCD算法能够有效地发现带权无向图中的重叠社区。
당전사구발현산법주요시침대무향도연구사구결구，단재실제복잡망락중，련접관계시상표현출비대칭성혹방향성，비여Twitter적용호관주관계，문헌망락적인용관계，망혈지간적초련접관계등응용망락。인차，본문의거신식재복잡망락중적전파규률화류동방향성，제출료k‐Path공사구린근상사성개념급계산방법，용우형량결점재동일사구적상사성정도，병급출료파유향도전환위대방향권치적무향도적방법。기우대권무향도제출료일충종국부확전래탐측사구적중첩사구발현산법（Local and wave‐like extension algorithm of detecting overlapping community ，LWS‐OCD）。재진실수거집상적실험표명，공사구린근상사성개념실현료유향도무향적합리전환，이차제고료사구결점적취집효과，LWS‐OCD산법능구유효지발현대권무향도중적중첩사구。
Most of the previous research on community detection are mainly based on the undirected graph structures .However ,in actual complex networks ,the links relation usually shows the asymmetric char‐acteristic or directionality ,such as citation network of scientific papers ,the one‐way follow relationship on Twitter ,and hyperlinks between web pages .Therefore ,based on the propagation of information and the direction of information transmission ,a k‐Path conception and calculation method for measuring the similarity of co‐community neighboring is presented to weigh possibility of nodes in the same community . Furthermore ,the method of transferring directed graphs into undirected graphs with similarity of weight is presented .Then the local extension algorithm of detecting overlapping community based on weighted undirected graphs is proposed .Several experiments on the real data sets are conducted and analyzed .Ex‐perimental results demonstrate that the k‐Path conception can achieve the reasonable conversion for di‐rected graph and improve the effectiveness of the community gathering nodes .Finally ,the results show that the algorithm can detect the overlapping community effectively .