Research On Overlapping Community Detection Method Based On Link Partition

The distribution of links in complex networks is locally inhomogeneous,with dense concentrations of links within special groups of nodes,and low concentrations between these groups.This property of the network is community structure.The communities in most real-world networks are overlapping.Compared with traditional communities,overlapping communities can reveal the concealed patterns more efficiently.Recently,the detection of overlapping communities has become one of the main challenges.Many algorithms have emerged among which one of the novel and effective idea was to regard the links instead of nodes as the research object.This unique method is defined as link partition.Although the new method has attracted much attention and the merits are indispensable,there still exist many demerits we cannot ignore.In the method of link partition,two nodes connected by one link only belong to one community which leads that the discovered communities are highly overlapped.To overcome this drawback,another method called Link Partition on Asymmetric Weighted Graph(LPAWG)is proposed in this work.In LPAWG,every link in the network is divided into two asymmetric weighted links.In addition,when translating the link community into node community,only the biased node is retained while the other one is neglected.This strategy make it possible that the two nodes linked by one link can belong to different communities.This is also the reason why LPAWG can be used to rationally detect overlapping communities.The scale of the weighted line graph matrix can be reduced by the fact that the community memberships of some links can be determined based on nonoverlapping community structure.We then propose the Accelerated LPAWG(ALPAWG)which applies the acceleration strategy on LPAWG.After the tests in both artificial benchmarks and real-world networks,it is noticeable that the accuracy of LPAWG is better than original link partition method.Moreover,ALPAWG can significantly reduce the scale of weighted line graph without affecting the accuracy.A method called Symmetric Non-negative Matrix Factorization based Link Partition(SNMF-Link)is proposed to fix the problem that the scale of the weighted line graph is too large.SNMF-Link is on the basis of that data can be represented by the subspace spaned by the link-node incidence matrix.This assumption can markedly reduce the scale of the unknown matrix.To solve the SNMF-Link,Multiplicative Update Rule(MUR)is proposed but the optimization algorithm of MUR converges slowly.So we propose another solution by applying Augmented Lagrangian Method(ALM)to SNMF-Link and solve it by the Optimal Gradient Method(OGM).The analysis of algorithm complexity shows that both SNMF-Link and ALM are effective.The experimental results in the benchmarks reveal that SNMF-Link takes less time without reducing the accuracy.What's more,SNMF-Link optimized by ALM takes less time than that optimized by MUR and normalized cut(Ncut)which is a classic spectral clustering method.