Research On Subgraph Structures Discovery In Social Networks

Social network is the network which takes social activities of human or organization as research objects,and abstracts the social activities as interactivities between individuals.Subgraph structures discovery from social network is very meaningful for understanding human society and important foundation of security analysis in social networks.The data produced in social network,which records the relationships between individuals,is called relational data.Graphs is one of the most widely studied instances of relational data.A graph may be either directed or undirected according to whether its edges(relationships)between vertices(individuals)are directed or undirected.Research on subgraph structures discovery in digraphs is more important than which in undirected graphs because undirected graphs can be easily converted into digraphs but not vice versa.For the information security,it is very necessary to mine the various subgraph structures existing in the social network.For example,the importance of the strong connected components in the multiagent collaborative system on the asymptotic convergence of the trust protocol,the risk of logical deadlocks caused possiobly by the cycles in the encrypted information transmission network,and even road safety patrol path planning and other issues.The most frequently used methods for the subgraph structures discovery in digraphs are the graph theory approaches.However,graph theory is not an effective tool for handling uncertain relational data.In contrast to graph theory,rough sets theory(RST)is a useful mathematical tool to handle uncertain and ambiguous information.Recently,the research on subgraph structures discovery based RST thus attracted the attention of many scholars.Thus,this dissertation focuses on discovering knowledge from digraphs,a kind of relational data,via RST and graph theory.The main contributions of this dissertation are listed as follows:(1)On dealing with digraphs,the correspondence relationship between rough sets theory and graph theory is characterized.And an algorithm to find strongly connected components of simple digraphs is proposed based on rough sets theory,as well as its parallel implementation.RST is a useful mathematical tool for handling uncertain information,which can discover knowledge from attribute data.However,for digraphs which is a kind of relational data,there are not RST-based approaches to handle it,not to mention for uncertain digraphs.In order to break through the limitations of classic RST in dealing with digraphs for subgraph structures discovery,based on the mutual representation between binary relations and digraphs,the correspondence relationship between RST and graph theory is characterized;Then,instructed by the correspondence relationship,aiming at discovering SCCs,a kind of subgraph structure,from digraphs,an algorithm called RSCC is proposed for finding SCCs of simple digraphs based on RST.Then the parallel implementation ofRSCC algorithm(PRSCC)is proposed for improving the efficiency of SCCs discovery.The results of the experimental analysis validate the validity and competitiveness on efficiency of two proposed algorithms.The proposing of the two algorithms firstly enable RST to process simple digraphs for subgraph structures discovery,provide theoretical basis for discovering subgraph structures from uncertain digraphs in future.(Chapter 2)(2)With granulating the vertex set of digraphs,an algorithm to find SCCs of simple digraphs based on granulation strategy is proposed to improve the deficiency of discovering SCCs.The correspondence relationship between RST and graph theory is the theoretical basis of applying RST to subgraph structures discovery in relational data.In order to investigate the reasonability that RSCC algorithm uses two RST operators,6)-step -related set and 6)-step upper approximation,to discover SCCs,we explore the equivalence between the two RST operators and BFS which is one of the most basic graph search algorithms and the most direct way to find SCCs.These two equivalence enrich the correspondence relationship between RST and graph theory.In addition,it is found that there are three SCCs correlations between vertices after we use three RST concepts,R-related set,lower and upper approximation sets to analyze SCCs.According to these three SCCs correlations,a granulation strategy is proposed.Then by combining RSCC algorithm with the granulation strategy,an algorithm called GRSCC for finding SCCs of simple digraphs based on granulation strategy is proposed.Experimental results show that GRSCC can discover SCCs more efficiently.(Chapter 3)(3)Based on heuristic depth-first search(DFS),an algorithm called HL-DPC is proposed to list the directed cycles in SCCs.HL-DPC algorithm is applied to the encrypted information transmission network,then can provide a feasible solution for detecting logical deadlock.Directed cycles is an important subgraph structure in digraphs and a special case of SCCs.Thus a directed cycle can be definitely discovered in a nontrivial SCC.Based on this fact,an algorithm called HL-DPC to discover directed cycles is proposed based on heuristic DFS.Furthermore,HLDPC algorithm is applied to the encrypted information transmission network,to provide a feasible solution for detecting logical deadlock.The experimental results illustrate the effectiveness of the algorithm and the necessity of using heuristic information to improve the mining efficiency.(Chapter4)(4)A symmetric metric based on vertex coordinate is proposed to evaluate the symmetric extent of visualized results.A force-directed graph drawing algorithm is proposed to visualize two subgraph structures,directed cycles and star-subgraphs,in digraphs.Relational data visualization is one of the branches of subgraph structures discovery in relational data.Graph drawing is the research on visualizing relational data.Firstly,symmetry is one of the mostimportant aesthetic criteria on graph drawing.It is quite necessary to measure the extent to which the drawings can be considered symmetric.For this purpose,a symmetric metric based on vertex coordinate calculation is proposed,then it is proven theoretically and validated experimentally that the proposed metric conforms to human perception of symmetry.Secondly,directed cycles and starsubgraphs are two common structures in digraphs and have inherent symmetry.From the viewpoint of knowledge discovery,the two structures should be eye-catching in the visualization results.From the viewpoint of visualization quality,the two structures should be displayed as symmetrically and eye-catching as possible.For this purpose,a force-directed algorithm named FDS is proposed.A series of experiments are carried out,it is found that for the digraphs containing directed cycles and star-subgraphs,the drawings produced by FDS algorithm can show directed cycles and star-subgraphs distinguished and have better values in the symmetric metric.The comparisons of consumption time also show the advantage of the algorithm in efficiency.(Chapter 5)...