Research On The Explanation Method Of The Why-not Problem On Graph Structural Clustering

Structural graph clustering is very important for managing and analyzing graph data.As an effective and useful graph clustering algorithm,SCAN is widely used to discover meaningful clusters in many different graph applications,such as social networks,communication networks,collaboration networks,gene networks,and so on.However,dirty data exists in graph data,for example,some edges are missing in graph data.In this case,the clustering results of SCAN over the dirty graph data cannot meet the users'requirements,such as,the expected nodes are missing in the desired clusters.In response to this phenomenon,users will ask why the existed graph structure clustering method can not return the results they want,and how to do can let the expected nodes appear in the query results,this kind of problem is called the why-not problem.Solving the why-not problem is to find a reasonable explanation for missing tuples in the clustering results,which can not only help users better understand the clustering results,but also improve the quality and availability of the database.To solve this problem,first,this graduation thesis explores an effective explanation model to make the expected nodes appear in the desired clusters.The model of explaining expected nodes in use the data modifification to explain why the expected nodes are not included in the desired clusters and how to make the expected nodes appear in the corresponding desired clusters by modifying the original graph dataset.To achieve this purpose,first,analyze the clustering rational of SCAN algorithm,and an unifified explanation framework is proposed based on the analysis above.Moreover,in order to retain the original clustering results in the new clustering results to the maximum extent,this graduation thesis proposes a penalty model and defines a penalty function to quantify the penalty of method of the why-not problem on graph Structural clustering.Then,this graduation thesis proposes two explanation algorithms,the basic interpretation algorithm for why-not problem and the improved interpretation algorithm for why-not problem,making the expected nodes appear in the desired clusters by modifying the original graph dataset with minimum penalty value.Finally,a large number of experiments are carried out in this graduation thesis on real data sets,and the experimental results show that the proposed method can effectively interpret the expected nodes of clustering results.According to theoretical analysis and experimental verification,this graduation thesis shows the efficiency and stability of the algorithm.