3
$\begingroup$

Given a graph like e.g.,

gr = Graph[{UndirectedEdge[1, 2], UndirectedEdge[1, 3], 
     UndirectedEdge[2, 3], UndirectedEdge[1, 4], UndirectedEdge[2, 4], 
     UndirectedEdge[3, 4], UndirectedEdge[1, 5], UndirectedEdge[2, 6], 
     UndirectedEdge[3, 6]}]

enter image description here

I would like to have a function trim that would remove vertices from this graph such that a maximum number of vertices remains which are all connected to each other:

gr2 = trim[gr]
gr2//FullForm

enter image description here Graph[List[1,2,3,4],List[UndirectedEdge[1,2],UndirectedEdge[1,3],UndirectedEdge[2,3],UndirectedEdge[1,4],UndirectedEdge[2,4],UndirectedEdge[3,4]]]

Does Mathematica have such a function? Or is there a quick way to write it using Mathematica functionality? Thanks for any suggestion.

$\endgroup$
  • 2
    $\begingroup$ What you are looking for is a clique, and finding a maximal clique can be accomplished with FindClique, if you are after that. This can be very computationally intensive. If you are looking for a clique of certain size there wouldn't appear to be a built-in function. I did ponder about the problem in mathematica.stackexchange.com/questions/97725/… ... $\endgroup$ – kirma Jan 13 at 16:09
  • 4
    $\begingroup$ @kirma IGraph/M can find cliques of a given size (not necessarily maximal) very efficiently: IGCliques. $\endgroup$ – Szabolcs Jan 13 at 16:34
  • 2
    $\begingroup$ The question is unclear. "remove all vertices from this graph which are not fully connected to all other vertices" --> Why did you not remove vertex 1? It is not connected to all other vertices. It is not connected to 6. $\endgroup$ – Szabolcs Jan 13 at 16:36
  • 3
    $\begingroup$ Maybe what you are looking for is a clique cover, i.e. partitioning the vertices into cliques? IGraph/M has IGCliqueCover. Be sure to look it up in the documentation which discusses the Method option. $\endgroup$ – Szabolcs Jan 13 at 17:28
  • 1
    $\begingroup$ @kirma Thank you, I'll take a look at FindClique. The maximal one should be sufficient for me. $\endgroup$ – Kagaratsch Jan 13 at 18:25
5
$\begingroup$

I would like to have a function trim that would remove vertices from this graph such that a maximum number of vertices remains which are all connected to each other:

You are looking for a largest clique. It can be done with

FindClique[g]

To find all largest cliques, use

FindClique[g, Length /@ FindClique[g], All]

IGraph/M also has a function for this, IGLargestCliques, and several other clique-related functions. For example, you can partition the graph into a smallest number of cliques:

SeedRandom[123]
g = RandomGraph[{10, 40}]

HighlightGraph[
 Graph[g, EdgeStyle -> LightGray],
 Style[Subgraph[g, #], Thick] & /@ IGCliqueCover[g]
]

enter image description here

As in this example, some of the components may have only one vertex. Also note that the components may not be largest or even maximal cliques. What this function does is it tries to minimize the number of components, not maximize the size of the largest component. If you want the largest component to be as large as possible, you could use

comps = First@
  Last@Reap@
    NestWhile[VertexDelete[#, Sow@First@FindClique[#]] &, g, 
     VertexCount[#] > 0 &]

(* {{1, 3, 4, 5, 6, 7, 10}, {2, 9}, {8}} *)

HighlightGraph[
 Graph[g, EdgeStyle -> LightGray],
 Style[Subgraph[g, #], Thick] & /@ comps
 ]

enter image description here

$\endgroup$
  • $\begingroup$ Thank you! Is there a link to the IGraph/M? I seem to be finding somewhat unrelated things when googling for it. $\endgroup$ – Kagaratsch Jan 13 at 18:43
  • 3
    $\begingroup$ @Kagaratsch Added link. What did you find when you googled? IGraph/M is not needed for this though. If all you want is a largest clique, you can just use FindClique. $\endgroup$ – Szabolcs Jan 13 at 18:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.