The Method Of Computing P-values Of Network Communities And Its Application

Network community structure is one of the most important features in complex networks,which can be used to investigate the organization or the hierarchy of network structures.Although there are many efforts on researching the network communities,most of them usually give an objective function which is used to define or evaluate the network communities.However,most of these objection functions do not address the statistical significance of communities.The p-value based on the hypothesis testing is a universally understood measure between 0 and 1.As a result,the threshold for the p-value is easy to specify since it corresponds to the significance level,while other objective functions are generally data-dependent.This paper has mainly done two tasks:(1)this paper proposes an upper bound of the p-value under the configuration model,and gives a detailed derivation process;(2)this paper proposes the exact analytical p-value under the Erd?s-Rényi model,and gives a detailed derivation process.Compared with other existing objective functions that measure the statistical significance of communities,the two calculation methods proposed by this paper are both analytical methods which directly evaluate one single community,without relying on the probability that each vertex belongs to this community and the reliance on the sampling techniques.In order to demonstrate the effectiveness of these two p-values,this paper also presents a community detection algorithm based on the seed expansion,and adopts these two p-values as the objective function in community detection.This paper chooses both traditional community detection algorithms and statistically significant community mining algorithms for comparison,the experiments results on both real data sets and simulated networks show that the results based on the proposed p-values are comparable with the competing methods which demonstrate the effectiveness of the proposed p-values.Furthermore,in order to demonstrate the advantage of employing the p-values,this paper also constructs experiments in which the traditional objective functions are employed in our community detection algorithm.The experimental results show that the proposed p-values can yield better performance than the tradition objective functions on most data sets.