5
$\begingroup$

I have a network of N sensors and a test that tells me whether two sensor outputs are definitely not causally related. This allows me to construct a causality graph where each sensor is a vertex and two vertices share an edge if they have passed the test.

Naturally, I'm looking for large cliques to see if the sensor network got anything of note. Causality graphs for one of the event types that I observe have an interesting property: they have one big clique and a set of vertices that are adjacent to the clique, but not each other. Like nodes 4 and 5 here:

example graph

Is there an optimal way to count these vertices? Right now I simply look for one-element subtractions of large cliques, but there is probably a body of work on the subject.

More generally, what kind of graph property am I dealing with and what terminology should I look up?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Additional information about the sensor network may help, as finding the largest clique is NP-hard for general graphs. $\endgroup$
    – LeechLattice
    Commented May 27, 2019 at 16:14
  • 1
    $\begingroup$ It's a photomultiplier array for detecting Cerenkov radiation from muons and EM showers. The causality test is designed for a model of a single muon, but for showers or muon bundles it provides the kind of a graph as described above. $\endgroup$
    – monday
    Commented May 27, 2019 at 16:20
  • $\begingroup$ I mean the structural properties of the sensor network, e.g. is it a perfect graph, a cograph, or it just looks like a random graph? $\endgroup$
    – LeechLattice
    Commented May 27, 2019 at 16:24
  • $\begingroup$ Ah, I missed the largest clique part. I already enumerate cliques with Bron-Kerbosch search, then check the cliques for these kind of vertices. But I thought there's a more optimal or established way to that, since I'm probably not the first guy to deal with this problem. $\endgroup$
    – monday
    Commented May 27, 2019 at 16:25
  • $\begingroup$ What about using cliquer? $\endgroup$
    – LeechLattice
    Commented May 27, 2019 at 16:26

1 Answer 1

Reset to default
2
$\begingroup$

You want to find independent sets (or the maximal size of an independent set) in the subgraph induced by the common neighbors of the vertices of a clique.

More specifically, if $K$ is a clique in the graph $G$ and $S$ is the set of vertices which are adjacent to each vertex of $K$, then any independent set of the induced subgraph $G[S]$ will give a set of vertices which are adjacent to vertices of the clique but not adjacent to each other.

In the special case when the clique contains a single vertex $v$, the problem is to find the maximum size of an independent set in the induced subgraph $G[\Gamma(v)]$, where $\Gamma(v)$ is the set of neighbors in $G$ of vertex $v$. This quantity seems NP-hard to compute because given a graph $H$, the maximum size of an independent set of $H$ can be obtained by adding a new vertex $v$ and joining $v$ to each vertex of $H$, and then computing in this new graph the maximum number of vertices adjacent to $v$ which are not adjacent to each other.

This invariant (for the $|K|=1$ case) reminds me of the induced star number or interference degree of a graph, and has appeared in recent literature in wireless adhoc networks - the worst-case performance of certain distributed algorithms in wireless sensor networks is a factor of exactly this quantity away from optimal; see https://arxiv.org/abs/1810.04109 and the references therein.

Improve this answer
$\endgroup$

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