2013 | OriginalPaper | Chapter
Mining Graphs of Prescribed Connectivity
Author : Natalia Vanetik
Published in: Knowledge Discovery, Knowledge Engineering and Knowledge Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Many real-life data sets, such as social, biological and communication networks are naturally and easily modeled as large labeled graphs. Finding patterns of interest in these graphs is an important task, but due to the nature of the data not all of the patterns need to be taken into account. Intuitively, if a pattern has high connectivity, it implies that there is a strong connection between data items. In this paper, we present a novel algorithm for finding frequent graph patterns with prescribed connectivity in large single-graph data sets. We also show how this algorithm can be adapted to a dynamic environment where the data changes over time. We prove that the suggested algorithm generates no more candidate graphs than any other algorithm whose graph extension procedure we employ.