The Algorithm To Enumerate Maximal K-Plexus In Network And The Resume Mining Of Community In Network

Graph Mining has became the focus of Data Mining. Graph Mining has many utility because graph-structed data occur widely in practical fields like biology, chemistry, communication and sociology. One network feature that has been emphasized in recent work is community structure, the gathering of vertices into groups such that there is a higher density of edges within groups than between them. Community is a powerful tool for understanding the structure and the functioning of the network, and its growth mechanisms. This thesis focuses on the analysis of network community and contains two parts as below.The first part is on the mining of maximal k-plexus. k-plex is one of many definitions of network community. Some methods and applications which use k-plex analysis have been proposed recently. However, these methods and applications can only analyze small networks because of the lack of effective k-plex mining algorithm. Thus, we propose a backtrack algorithm for enumerating all the maximal k-plexus and some prune strategies to improve the performance of algorithm. A parallel edition of the algorithm and a task schedule strategy is stated to analyze larger network. We also propose some approximal algorithm strategies to speed up our method. In addition, we evaluate the performance of our algorithm and the effect of strategies on random graphs.The second part is on the resume mining of network community. In order to understand the structure and dynamics of communities and utilize their information, we propose the problem of resume mining of network community. We also study three important problems of resume mining: the characterization of community , the discrimination among communities and the community evolution mining. The characterization of community mines the ultimate cause of the formation of the community; the discrimination among communities extracts the unique features of one community; the community evolution mining mines the evolution history of a community in several successive network snapshot. Finally, two cases of community resume mining are studied to demonstrate the effect of our algorithm.