5
$\begingroup$

Bug introduced in 9.0 and persisting through 12.1
FindKPlex is new in 9.0.

I have an example about it.

g = Graph[{1 -> 4, 1 -> 7, 1 -> 9, 1 -> 16, 2 -> 5, 2 -> 6, 2 -> 8, 2 -> 18, 
 2 -> 20, 5 -> 9, 5 -> 12, 5 -> 14, 5 -> 20, 5 -> 22, 6 -> 11, 
 6 -> 20, 7 -> 6, 7 -> 17, 7 -> 22, 8 -> 2, 8 -> 5, 8 -> 6, 8 -> 10, 
 8 -> 13, 9 -> 3, 9 -> 6, 9 -> 7, 9 -> 8, 9 -> 10, 9 -> 18, 9 -> 20, 
 10 -> 8, 11 -> 2, 11 -> 3, 11 -> 5, 11 -> 6, 12 -> 7, 12 -> 13, 
 12 -> 15, 14 -> 11, 15 -> 10, 15 -> 16, 15 -> 17, 15 -> 19, 16 -> 1, 
 16 -> 13, 17 -> 2, 17 -> 10, 17 -> 14, 17 -> 15, 17 -> 21, 18 -> 2, 
 18 -> 8, 18 -> 11, 18 -> 13, 18 -> 19, 19 -> 3, 19 -> 16, 19 -> 17, 
 20 -> 3, 20 -> 4, 20 -> 10, 21 -> 1, 21 -> 6, 21 -> 19, 22 -> 5, 
 22 -> 10, 22 -> 11, 22 -> 12, 22 -> 18}];

re = FindKPlex[g, 2, {5}, All]
Subgraph[g, #, VertexLabels -> "Name"] & /@ re

Such as the sixth subgraph (after Szabolcs help to fixe.Thanks a lot again.).:

enter image description here

As the documentation's Details, we translate it for this graph--"For a directed graph, the outgoing edges for each vertex connect to all except 9,6(first two vertexes of the list) others. "But actually the number 10th vertex has no outgoing edges to connect with 20th.

Or this example in its documentation(I have changed its parameter.)

enter image description here

What is the result? Or this function has some mysterious bugs? Who can give a rational explanation about it?

Improve this question
$\endgroup$
5
  • $\begingroup$ Please don't post graphs like that ... it's impossible to see what's going on. Most people wouldn't even copy it. I fixed it for you. $\endgroup$
    – Szabolcs
    Mar 15, 2016 at 18:40
  • $\begingroup$ Thanks very much.This is my first to upload a Graph.But slightly strange that result have some little change(the odring of that vertexs). $\endgroup$
    – yode
    Mar 15, 2016 at 18:46
  • $\begingroup$ I didn't know what was a k-plex. That explanation in the documentation is really confusing. This is much better: analytictech.com/ucinet/help/1pdb_fw.htm $\endgroup$
    – Szabolcs
    Mar 15, 2016 at 18:50
  • $\begingroup$ I cannot make sense of this either. First, I think the description in the documentation is really hard to follow. But I understood it from the other link above. However, I cannot make sense out of the directed result $\endgroup$
    – Szabolcs
    Mar 15, 2016 at 18:55
  • $\begingroup$ Perhaps you mean that description of"each vertex of the induced subgraph is connected to at least n-k other vertices, where n is the number of vertices in the induced subgraph. The basic algorithm is a depth first search.".But there are some difference from the running result.Such as the sixth subgraph(after your fixed it).The number 10 vertex have no outgoing edges to connected with 20. $\endgroup$
    – yode
    Mar 15, 2016 at 18:58

1 Answer 1

Reset to default
3
$\begingroup$

I would appreciate if someone familiar with k-plexes would verify this answer.

In short

I think that FindKPlex treats directed graphs as undirected (except for 1-plexes), which goes against what the documentation says. I think this is a bug.

Long version

I did not know what a k-plex was. The documentation says:

A k-plex is a maximal set of vertices such that each vertex is adjacent to all except k others.

I find this hard to understand, so I googled and found this:

A k-plex is a maximal subgraph with the following property: each vertex of the induced subgraph is connected to at least n-k other vertices, where n is the number of vertices in the induced subgraph.

This is much more clear.

Let's take a graph.

g = RandomGraph[{10, 20}];

Let's find a 2-plex of size 4 in it ...

{twoplex} = FindKPlex[g, 2, {4}]
{{1, 2, 3, 9}}

... and get the corresponding induced subgraph:

sg = Subgraph[g, twoplex]

This subgraph is of size $n=4$. It's a 2-plex, thus each vertex must have degree at least $n-2 = 4-2 = 2$. Is this true?

VertexDegree[sg]
(* {2, 3, 2, 3} *)

As many times as I try it, it seems to be true, so I believe Mathematica uses this definition as well. But the definition in Mathematica's documentation never says "at least", so I find it confusing.

Now what about directed graphs? From the documentation:

For a directed graph, the outgoing edges for each vertex connect to all except k others.

It sounds like the definition is the same as for undirected ones, but now it is the out-degree that must be greater than or equal to $n-k$.

Is this the case?

g = RandomGraph[{10, 20}, DirectedEdges -> True];

VertexOutDegree@Subgraph[g, #] & /@ FindKPlex[g, 2, {4}, All]

{{2, 1, 2, 1}, {1, 0, 2, 2}, {0, 1, 2, 1}, {1, 1, 0, 2}, {1, 1, 2, 
  0}, {2, 1, 2, 1}, {2, 0, 2, 2}, {2, 1, 2, 2}}

No, it is not! Some out-degrees are less than 2. The same is true for in-degrees.

What is happening then?

Well, for any directed graph g I tried, the directed result is exactly the same as the undirected result. Except for 1-plexes!

Table[
 g = RandomGraph[{10, 20}, DirectedEdges -> True];
 Table[
  FindKPlex[UndirectedGraph[g], k, Infinity, All] == 
   FindKPlex[g, k, Infinity, All],
  {k, 1, VertexCount[g]}
  ],
 {10}
 ]

{{False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}, {False, True, True, True, True, True, True, True, True, 
  True}}

Conclusion: FindKPlex does not really support directed graphs, it just treats them as undirected, except for 1-plexes.

But the documentation says,

FindKPlex works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

and also explicitly specifies what should happen for directed graphs (quotation above). So I think this is a bug.

But I would appreciate if someone actually familiar with k-plexes would verify that I am right.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you upload your Graph that what you have used? $\endgroup$
    – yode
    Mar 15, 2016 at 19:32
  • $\begingroup$ @yode No, it's gone. It was randomly generated. $\endgroup$
    – Szabolcs
    Mar 15, 2016 at 19:36
  • $\begingroup$ I'm try to understand your introductions.But my random graph is difference to yours perhaps. $\endgroup$
    – yode
    Mar 15, 2016 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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