Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of non-edges within $X$ plus the number of edges from $X$ to the outside, all this divided by $|X|$. Intuitively, it is the number of edges to add/delete so that $X$ becomes an isolated clique, divided by $|X|$.

To put it formally, for $X, Y \subseteq V$, possibly overlapping, denote

$$E(X, Y) = \{\{u,v\} : u \in X, v \in Y, uv \in E\}$$

Also denote $$\overline{E(X, Y)} = \{\{u,v\} : u \in X, v \in Y, u \neq y, uv \notin E\}$$

I would like to find the subset $X \subseteq V(G)$ that minimizes

$$ \frac{|E(X, V \setminus X)| + |\overline{E(X, X)}|}{|X|} $$

Is there anything in the literature about this? I'd like to know if it's NP-hard, approximable, etc.

This relates to the densest subgraph problem, which can be found in polynomial time. But densest subgraph ignores the outside edges. Densest subgraph exploits a supermodular formulation, which does not apply here.There are also some (actually lots) of community detection papers out there, but I haven't found one that deals with this particular cost.

  • 1
    $\begingroup$ Interesting question! The divide by $|X|$ makes it slightly unusual for me. I don't know anything, but I was immediately reminded of a concept called Integrity, or vulnerability measures. I'm not sure it's going to help you, but you can look in the literature, e.g. A Survey of Integrity for things that might be related. Other concepts are toughness and covering number. Integrity is also sometimes referred to as Component Order Connectivity, eg A survey of component order connectivity models... by Gross et al $\endgroup$
    – Pål GD
    Sep 17 '18 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.