An Improved Greedy Louvain Method And Its Applications

The community in networks is thought of as a set of nodes where nodes are densely interconnected and sparsely linked to other parts of the networks.The research of community structure in networks has positive theoretical and practical effects on understanding topology structure of networks and learning the functions of networks.The detection of community structure is widely applied into social networks,research of merchandising,terroristic organization uncovered,biological network analysis,clustering of Web document,search engine,etc.Community structure detection has become focus of interdisciplinary research area.This paper proposes ILouvain(Improved Louvain)basing on greedy Louvain(hereafter referred as Louvain)and uses it to improve graph signal denoising and quality assessment.Firstly,the algorithm ILouvain is proposed.Louvain is a fast community detection method for large work,but it can’t recognize some small communities due to the limitation of method basing on modularity optimization.To overcome the limitation,we set a threshold of modularity.When the modularity of subgraph is greater than the threshold,we segment the subgraph continuously.the modularity of null model of different graph is disparate,but they all focus on a small range respectively.From the above the modularity of null model adding a small number is a threshold.Experiment results show ILouvain method can output those small community more accurately.Secondly,this paper proposes the group idea to improve graph signal denoising result.Combination of community detection and other graph processing can obtain a better result in some condition.For example,detect community and then process community respectively.We introduce the group idea into a set of denoising method.communities are grouped according the mean of signal on it,then the edges between different groups are removed.The experiment result shows the method preserves the high frequency well and improves the PSNR significantly.At last,the algorithm which is named GSSIM(Graph Structure Similarity)is proposed.The quality matric of graph signal denoising result is usually PSNR(Peak Signal to Noise Ratio).It is simple to compute and has clear physical meanings.There is community structure in graph and every community may have central and marginal node,which may mean different importance.In another word,the quality variation may be different when add same noisy to nodes with different degree.This paper proposes GSSIM,inspiring by structure similarity of image to make graph signal matric match special structure of graph signal.GSSIM is computed based on community and weighted by edge weight.The experiment result shows GSSIM can be an alternative metric of graph signal quality assessment.