Fouille de grands graphes.
Mostafa Haghir Chehreghani · HAL (Le Centre pour la Communication Scientifique Directe) · 2016
During the last decade or so, the amount of data that is generated and becomespublicly available is rapidly growing. This makes it impossible to extract usefulinformation from this huge amount of data manually without using automatic toolsand algorithms. Data mining has been defined as the process of automatic extractionof useful and previously unknown information from a large dataset using techniquesfrom statistics, artificial intelligence and database management. Furthermore, in manyapplications, such as Bioinformatics, the world wide web, social and technologicaland communication networks, data are usually represented with graphs. This makesgraph mining practically interesting, while also a challenging research area, dueto high computational cost involved in processing graph data. In this dissertation,we investigate two key problems in graph mining: frequent pattern mining andbetweenness centrality computation.Existing algorithms for finding frequent patterns from large single networks mainlyuse subgraph isomorphism. However, subgraph isomorphism is expensive to compute:deciding whether one graph is subgraph isomorphic to another graph is NP-completein terms of the sizes of the graphs. Recently, a few algorithms have used subgraphhomomorphism. However, they find very restricted classes of patterns such as trees.The main challenge with pattern mining under subgraph homomorphism is the patterngeneration phase. In this work, we go beyond trees and propose an efficient algorithmfor mining graph patterns from large networks under homomorphism. We introduce anew class of patterns, called rooted graphs, and present an algorithm for completegeneration of rooted graphs. We also propose a new data structure for compactrepresentation of all frequent patterns. By performing extensive experiments onseveral real-world and synthetic large networks, we show the empirical efficiency ofour proposed algorithm, called HoPa.We then present an efficient algorithm for subtree homeomorphism with applicationto frequent pattern mining. We propose a compact data-structure, called occ, that canencode and represent several occurrences of a tree pattern and define efficient joinoperations on the occ data-structure, that help us to count occurrences of tree patternsaccording to occurrences of their proper subtrees. Based on the proposed subtreehomeomorphism method, we develop an effective pattern mining algorithm, calledTPMiner. We evaluate the efficiency of TPMiner on several real-world and syntheticdatasets. Our extensive experiments confirm that TPMiner always outperforms well-known existing algorithms, and in several cases the improvement with respect toexisting algorithms is significant.Finally, we propose a randomized algorithm for unbiased estimation of betweennesscentrality. We discuss the conditions that a promising sampling technique shouldsatisfy to minimize the approximation error. We then propose a sampling method thatfits better with these conditions. By performing extensive experiments on syntheticand real-world networks, we compare our proposed method with existing algorithmsand show that our method works with a better accuracy.