Increase score with number of nodes

Question

I'm trying to define a normalized scoring algorithm for undirected graphs and I have decided to use graph density as the base of this.

So accordingly, the score of the 1st is 67% and 2nd is 33%. But I want to get a higher score for the second graph since the number of "S" nodes are higher (Assume there is a method to identify the S nodes and C nodes and edges)

If I simply multiply the current score with the number of nodes, the result is not normalized. And there is no way to bound the number of S nodes (it can be any positive value)

Answer 1

I assume that a graph $G$ has $n$ nodes, $s$ $S-$nodes, and $m$ edges. The score $C(G)$ depends how valuable is the number $s$ and how score depends of it. A simple way to take into account both $m$ and $s$ is to put

$$C(G)=\frac {4m}{n(n+1)}+ \frac {2s}{n}.$$

Then $0\le C(G)\le 1$ for each $G$ and $C=1$ iff $G$ is a complete graph all whose nodes are $S$-nodes.