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.