Research On Community Detection And Search Algorithms In Uncertain Graphs

As a general data structure for modeling large-scale network,Graphs have been widely concerned by academics.Many kinds of data can be abstracted into graphs,such as transportation networks,social networks,biological networks,collaborative networks,communication networks and so on.Due to the noise and errors that may occur at any time during the process of data collection and processing,some graph data are uncertain.Therefore,the academic community has started to pay attention to the problem of community mining in uncertain graphs recently.Uncertain graphs can be obtained by adding a probability dimension to certain graphs,which can express richer semantics and better represent the inherent uncertainty of the data itself.However,due to the extra probability dimension of uncertain graphs,this also leads to the result that the research results in certain graphs cannot be directly applied to uncertain graphs.In this dissertation,this paper focuses on the community detection problem based on k-median and k-center clustering in uncertain graphs and the community search problem considering node influence in uncertain graphs.For the community detection problems based on k-median and k-center clustering in uncertain graphs,we analyze the hardness of these problems and propose algorithms that provide considerably improved approximation guarantees than the existing studies do.Specifically,our algorithms offer a(1-1/e)-approximations for the k-median prob-lem,and(OPTkc)-approximations for the k-center problem,where OPTkc is the optimal objective function value for k-center.In addition,our algorithms incorporate several non-trivial optimizations that significantly enhance their practical efficiency.Exten-sive experimental results demonstrate that our algorithms considerably outperform the existing methods on both computation efficiency and the quality of the returned solu-tion.For the problem of community search considering node influence in uncertain graphs,all the previous studies on this problem do not consider the uncertainty of graphs.In this paper,we introduce a novel community model called in fluential(k,?)-community based on the concept of(k,?)-core.Based on the new community model,we propose an online local search algorithm SearchIC.Extensive empirical studies on real graphs demonstrate that our algorithms outperform the existing online search algo-rithms by several orders of magnitude.