Finding large -clubs in undirected graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2012-12-23

AUTHORS

Maw-Shang Chang, Ling-Ju Hung, Chih-Ren Lin, Ping-Chen Su

ABSTRACT

Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-clique, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-clan. The concept of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club is one of them. A \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}. It is a relaxation of a clique, which induces a subgraph of diameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}. We conducted algorithmic studies on finding a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of size as large as possible. In this paper, we show that one can find a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.62^n)$$\end{document} time where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-DN which, under deletion of vertices from a graph, maintains for a given vertex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} the set of vertices at distances at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}. From the experimental results that we obtained, we concluded that a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-clubs of maximum size in most of experimental instances. The gap between the size of a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size and a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club found by IDROP is a constant for the number of vertices that we are able to test. More... »

PAGES

739-758

References to SciGraph publications

  • 2012. Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs in PARAMETERIZED AND EXACT COMPUTATION
  • 1979-04. Cliques, clubs and clans in QUALITY & QUANTITY
  • 2005-08. Novel Approaches for Analyzing Biological Networks in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 1950-06. Connectivity and generalized cliques in sociometric group structure in PSYCHOMETRIKA
  • 2010. Approximating Maximum Diameter-Bounded Subgraphs in LATIN 2010: THEORETICAL INFORMATICS
  • 2012-03-22. Algorithms for the maximum k-club problem in graphs in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 2011-04-05. Parameterized computational complexity of finding small-diameter subgraphs in OPTIMIZATION LETTERS
  • 1993-12. Solving the maximum clique problem using a tabu search approach in ANNALS OF OPERATIONS RESEARCH
  • 1997. Semi-dynamic shortest paths and breadth-first search in digraphs in STACS 97
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00607-012-0263-3

    DOI

    http://dx.doi.org/10.1007/s00607-012-0263-3

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1014459099


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, HungKuang University, 43302, Sha Lu, Taichung, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.411432.1", 
              "name": [
                "Department of Computer Science and Information Engineering, HungKuang University, 43302, Sha Lu, Taichung, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chang", 
            "givenName": "Maw-Shang", 
            "id": "sg:person.013174232477.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, HungKuang University, 43302, Sha Lu, Taichung, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.411432.1", 
              "name": [
                "Department of Computer Science and Information Engineering, HungKuang University, 43302, Sha Lu, Taichung, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hung", 
            "givenName": "Ling-Ju", 
            "id": "sg:person.014652573161.60", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014652573161.60"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Min-Hsiung, Chiayi, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Min-Hsiung, Chiayi, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lin", 
            "givenName": "Chih-Ren", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Min-Hsiung, Chiayi, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Min-Hsiung, Chiayi, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Su", 
            "givenName": "Ping-Chen", 
            "id": "sg:person.016707640317.51", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016707640317.51"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0023446", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010738754", 
              "https://doi.org/10.1007/bfb0023446"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02023002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000623908", 
              "https://doi.org/10.1007/bf02023002"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-12200-2_53", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053025964", 
              "https://doi.org/10.1007/978-3-642-12200-2_53"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02289199", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041252991", 
              "https://doi.org/10.1007/bf02289199"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-012-9473-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003980818", 
              "https://doi.org/10.1007/s10878-012-9473-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-33293-7_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048244379", 
              "https://doi.org/10.1007/978-3-642-33293-7_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00139635", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032631481", 
              "https://doi.org/10.1007/bf00139635"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-005-1857-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038273169", 
              "https://doi.org/10.1007/s10878-005-1857-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11590-011-0311-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037149016", 
              "https://doi.org/10.1007/s11590-011-0311-5"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012-12-23", 
        "datePublishedReg": "2012-12-23", 
        "description": "Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-clique, and \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-clan. The concept of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club is one of them. A \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}. It is a relaxation of a clique, which induces a subgraph of diameter \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$1$$\\end{document}. We conducted algorithmic studies on finding a \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club of size as large as possible. In this paper, we show that one can find a \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club of maximum size in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O^{*}(1.62^n)$$\\end{document} time where \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$n$$\\end{document} is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-DN which, under deletion of vertices from a graph, maintains for a given vertex \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$v$$\\end{document} the set of vertices at distances at most \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}. From the experimental results that we obtained, we concluded that a \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-clubs of maximum size in most of experimental instances. The gap between the size of a \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club of maximum size and a \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k$$\\end{document}-club found by IDROP is a constant for the number of vertices that we are able to test.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00607-012-0263-3", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1297324", 
            "issn": [
              "0010-485X", 
              "1436-5057"
            ], 
            "name": "Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "9", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "95"
          }
        ], 
        "keywords": [
          "social networks", 
          "experimental instances", 
          "cohesive subgroups", 
          "program", 
          "important issue", 
          "concept", 
          "network", 
          "issues", 
          "study", 
          "subgroups", 
          "time", 
          "model", 
          "results", 
          "instances", 
          "gap", 
          "cliques", 
          "set", 
          "paper", 
          "number", 
          "experimental results", 
          "subset", 
          "size", 
          "algorithmic study", 
          "structure", 
          "distance", 
          "relaxation", 
          "algorithm", 
          "maximal subset", 
          "graph", 
          "data structure", 
          "branches", 
          "vertices", 
          "reasonable time", 
          "deletion", 
          "diameter", 
          "maximum size", 
          "set of vertices", 
          "new heuristic algorithm", 
          "dense graphs", 
          "subgraphs", 
          "dynamic data structures", 
          "undirected graph", 
          "heuristic algorithm", 
          "sparse graphs", 
          "number of vertices", 
          "input graph", 
          "cohesive subgraphs", 
          "subgraph of diameter", 
          "combinatorial branch", 
          "deletion of vertices", 
          "IDROP"
        ], 
        "name": "Finding large -clubs in undirected graphs", 
        "pagination": "739-758", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1014459099"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00607-012-0263-3"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00607-012-0263-3", 
          "https://app.dimensions.ai/details/publication/pub.1014459099"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:17", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_557.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00607-012-0263-3"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00607-012-0263-3'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00607-012-0263-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00607-012-0263-3'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00607-012-0263-3'


     

    This table displays all metadata directly associated to this object as RDF triples.

    168 TRIPLES      22 PREDICATES      85 URIs      68 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00607-012-0263-3 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nf3b9c1d43dca42c38f593a369954c18d
    4 schema:citation sg:pub.10.1007/978-3-642-12200-2_53
    5 sg:pub.10.1007/978-3-642-33293-7_22
    6 sg:pub.10.1007/bf00139635
    7 sg:pub.10.1007/bf02023002
    8 sg:pub.10.1007/bf02289199
    9 sg:pub.10.1007/bfb0023446
    10 sg:pub.10.1007/s10878-005-1857-x
    11 sg:pub.10.1007/s10878-012-9473-z
    12 sg:pub.10.1007/s11590-011-0311-5
    13 schema:datePublished 2012-12-23
    14 schema:datePublishedReg 2012-12-23
    15 schema:description Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-clique, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-clan. The concept of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club is one of them. A \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}. It is a relaxation of a clique, which induces a subgraph of diameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}. We conducted algorithmic studies on finding a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of size as large as possible. In this paper, we show that one can find a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.62^n)$$\end{document} time where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-DN which, under deletion of vertices from a graph, maintains for a given vertex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} the set of vertices at distances at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}. From the experimental results that we obtained, we concluded that a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-clubs of maximum size in most of experimental instances. The gap between the size of a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club of maximum size and a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-club found by IDROP is a constant for the number of vertices that we are able to test.
    16 schema:genre article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf Nc029d09461df4490bdf85d8a777406b4
    20 Nd373767ca50f49aeba7989a5aede249c
    21 sg:journal.1297324
    22 schema:keywords IDROP
    23 algorithm
    24 algorithmic study
    25 branches
    26 cliques
    27 cohesive subgraphs
    28 cohesive subgroups
    29 combinatorial branch
    30 concept
    31 data structure
    32 deletion
    33 deletion of vertices
    34 dense graphs
    35 diameter
    36 distance
    37 dynamic data structures
    38 experimental instances
    39 experimental results
    40 gap
    41 graph
    42 heuristic algorithm
    43 important issue
    44 input graph
    45 instances
    46 issues
    47 maximal subset
    48 maximum size
    49 model
    50 network
    51 new heuristic algorithm
    52 number
    53 number of vertices
    54 paper
    55 program
    56 reasonable time
    57 relaxation
    58 results
    59 set
    60 set of vertices
    61 size
    62 social networks
    63 sparse graphs
    64 structure
    65 study
    66 subgraph of diameter
    67 subgraphs
    68 subgroups
    69 subset
    70 time
    71 undirected graph
    72 vertices
    73 schema:name Finding large -clubs in undirected graphs
    74 schema:pagination 739-758
    75 schema:productId Nccdb5cacf755460598f1b04317f6f83e
    76 Nd5bc6d269daa4b1da5c7c92dc7b6297e
    77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014459099
    78 https://doi.org/10.1007/s00607-012-0263-3
    79 schema:sdDatePublished 2021-11-01T18:17
    80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    81 schema:sdPublisher N13f04acc4f3a48df9d8f8a9ecc323c28
    82 schema:url https://doi.org/10.1007/s00607-012-0263-3
    83 sgo:license sg:explorer/license/
    84 sgo:sdDataset articles
    85 rdf:type schema:ScholarlyArticle
    86 N097ac2a92d154a47882015ec66a06901 rdf:first sg:person.014652573161.60
    87 rdf:rest Nd06e7c1cebd7492c863a067afa6470e1
    88 N13f04acc4f3a48df9d8f8a9ecc323c28 schema:name Springer Nature - SN SciGraph project
    89 rdf:type schema:Organization
    90 Nc029d09461df4490bdf85d8a777406b4 schema:volumeNumber 95
    91 rdf:type schema:PublicationVolume
    92 Nccdb5cacf755460598f1b04317f6f83e schema:name dimensions_id
    93 schema:value pub.1014459099
    94 rdf:type schema:PropertyValue
    95 Nd06e7c1cebd7492c863a067afa6470e1 rdf:first Nd6815f5c17104105b1bb129e7a6650e3
    96 rdf:rest Nf0c071a5fa4f492e9c51a635fca01ffd
    97 Nd373767ca50f49aeba7989a5aede249c schema:issueNumber 9
    98 rdf:type schema:PublicationIssue
    99 Nd5bc6d269daa4b1da5c7c92dc7b6297e schema:name doi
    100 schema:value 10.1007/s00607-012-0263-3
    101 rdf:type schema:PropertyValue
    102 Nd6815f5c17104105b1bb129e7a6650e3 schema:affiliation grid-institutes:grid.412047.4
    103 schema:familyName Lin
    104 schema:givenName Chih-Ren
    105 rdf:type schema:Person
    106 Nf0c071a5fa4f492e9c51a635fca01ffd rdf:first sg:person.016707640317.51
    107 rdf:rest rdf:nil
    108 Nf3b9c1d43dca42c38f593a369954c18d rdf:first sg:person.013174232477.45
    109 rdf:rest N097ac2a92d154a47882015ec66a06901
    110 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    111 schema:name Information and Computing Sciences
    112 rdf:type schema:DefinedTerm
    113 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    114 schema:name Computation Theory and Mathematics
    115 rdf:type schema:DefinedTerm
    116 sg:journal.1297324 schema:issn 0010-485X
    117 1436-5057
    118 schema:name Computing
    119 schema:publisher Springer Nature
    120 rdf:type schema:Periodical
    121 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.411432.1
    122 schema:familyName Chang
    123 schema:givenName Maw-Shang
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
    125 rdf:type schema:Person
    126 sg:person.014652573161.60 schema:affiliation grid-institutes:grid.411432.1
    127 schema:familyName Hung
    128 schema:givenName Ling-Ju
    129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014652573161.60
    130 rdf:type schema:Person
    131 sg:person.016707640317.51 schema:affiliation grid-institutes:grid.412047.4
    132 schema:familyName Su
    133 schema:givenName Ping-Chen
    134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016707640317.51
    135 rdf:type schema:Person
    136 sg:pub.10.1007/978-3-642-12200-2_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053025964
    137 https://doi.org/10.1007/978-3-642-12200-2_53
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-642-33293-7_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048244379
    140 https://doi.org/10.1007/978-3-642-33293-7_22
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/bf00139635 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032631481
    143 https://doi.org/10.1007/bf00139635
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/bf02023002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000623908
    146 https://doi.org/10.1007/bf02023002
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/bf02289199 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041252991
    149 https://doi.org/10.1007/bf02289199
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/bfb0023446 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010738754
    152 https://doi.org/10.1007/bfb0023446
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/s10878-005-1857-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1038273169
    155 https://doi.org/10.1007/s10878-005-1857-x
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/s10878-012-9473-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1003980818
    158 https://doi.org/10.1007/s10878-012-9473-z
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1007/s11590-011-0311-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037149016
    161 https://doi.org/10.1007/s11590-011-0311-5
    162 rdf:type schema:CreativeWork
    163 grid-institutes:grid.411432.1 schema:alternateName Department of Computer Science and Information Engineering, HungKuang University, 43302, Sha Lu, Taichung, Taiwan
    164 schema:name Department of Computer Science and Information Engineering, HungKuang University, 43302, Sha Lu, Taichung, Taiwan
    165 rdf:type schema:Organization
    166 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Min-Hsiung, Chiayi, Taiwan
    167 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Min-Hsiung, Chiayi, Taiwan
    168 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...