Skip to main content
Taylor & Francis Group Logo
    Advanced Search

    Click here to search products using title name,author name and keywords.

    • Login
    • Hi, User  
      • Your Account
      • Logout
      Advanced Search

      Click here to search products using title name,author name and keywords.

      Breadcrumbs Section. Click here to navigate to respective pages.

      Chapter

      Single-Graph Support Measures
      loading

      Chapter

      Single-Graph Support Measures

      DOI link for Single-Graph Support Measures

      Single-Graph Support Measures book

      Single-Graph Support Measures

      DOI link for Single-Graph Support Measures

      Single-Graph Support Measures book

      ByToon Calders, Jan Ramon, Dries Van Dyck
      BookQuantitative Graph Theory

      Click here to navigate to parent product.

      Edition 1st Edition
      First Published 2014
      Imprint Chapman and Hall/CRC
      Pages 22
      eBook ISBN 9780429103261
      Share
      Share

      ABSTRACT

      Over the last several years, graph mining has emerged as a new field within contemporary data mining. One of the central tasks is the search for subgraphs, called patterns, that occur frequently in either a collection of graphs (e.g., databases of molecules [6], game positions [15], scene descriptions) or in a single large graph

      (e.g., the Internet, citation networks [16], social networks [12], protein interaction networks [10]). In the literature, the terms frequency and support have been used interchangeably to denote the measure to quantify the prevalence of a pattern. In the single-graph setting, however, the notion of frequency is not at all straightforward to define. For example, the obvious definition of taking the number of instances of a pattern as its frequency has the undesirable property that extending the pattern (i.e., making it more restrictive) may actually increase its frequency. Indeed, consider for instance, the unlabeled k-clique Kk as the single graph in which we want to find patterns. There are

      ) different embeddings under subgraph isomorphism of the unla-

      beled path of length 1 in Kk, whereas there are 3 (k 3

      ) embeddings of the path of length

      2 in Kk. In fact, the number of different embeddings may increase exponentially in the size of the pattern. Hence, as pointed out by Vanetik et al. [17], a good frequency measure must be such that the frequency of a superpattern is always at most as high as that of a subpattern. This property is called the antimonotonicity. Also, for reasons of efficiency, antimonotonicity of the frequency measure is highly desirable, as it allows for pruning large parts of the search space in a general-to-specific exploration. The efficiency and correctness of most existing graph pattern miners relies critically on the antimonotonicity of the frequency measure being used.

      T&F logoTaylor & Francis Group logo
      • Policies
        • Privacy Policy
        • Terms & Conditions
        • Cookie Policy
        • Privacy Policy
        • Terms & Conditions
        • Cookie Policy
      • Journals
        • Taylor & Francis Online
        • CogentOA
        • Taylor & Francis Online
        • CogentOA
      • Corporate
        • Taylor & Francis Group
        • Taylor & Francis Group
        • Taylor & Francis Group
        • Taylor & Francis Group
      • Help & Contact
        • Students/Researchers
        • Librarians/Institutions
        • Students/Researchers
        • Librarians/Institutions
      • Connect with us

      Connect with us

      Registered in England & Wales No. 3099067
      5 Howick Place | London | SW1P 1WG © 2022 Informa UK Limited