Please assume you are replying to somebody with limited knowledge in mathematics. I am drawing a blank.

I made up a formula which quantifies how similar two graphs are G and G' (Conceptual Graphs to be precise), scaled between 0 and 1, with 0 being completely dissimilar, and 1 being identical, where nodes can belong to either a set of concepts C or a set of relations R (but not both):

\begin{equation} C_{G} \sim C'_{G'} = \frac{C(G \cap G')}{ \mid C_{G} \mid + \mid C_{G'} \mid }. \end{equation}

\begin{equation} R_{G} \sim R'_{G'} = \frac{R(G \cap G')}{ \mid R_{G} \mid + \mid R_{G'} \mid }. \end{equation}

\begin{equation} E_{G} \sim E'_{G'} = \frac{E(G \cap G')}{ \mid E_{G} \mid + \mid E_{G'} \mid }. \end{equation}

By obtaining the ratio of identical concepts, relations and Edges, I can calculate the normalised average graph similarity as shown below:

\begin{equation} G \sim G' = \frac{ (C_{G} \sim C'_{G'}) + (R_{G} \sim R'_{G'}) + (E_{G} \sim E'_{G'})}{3}. \end{equation}

This works, but it is biased towards nodes (concepts C and relations R), since the ratio of nodes to edges is 2:1.

Now assume I have some graph metric, e.g., 0.79 (or 79%) and I want to adjust it, so that the graph ratio for nodes and edges is 1:1, so that the change in the ratio reflects the change in the metric. I know that since the ratio is 2:1, thus 0.33 of 0.79 is attributed to edges, hence edges provide 0.26 of the total.

  1. How can I adjust the formula so that the ratio of Edges and Nodes is 1:1?
  2. Is it possible to adjust the actual value (e.g., 0.79) to reflect the ratio change, while keeping it normalised between 0 and 1?

I don't know what exactly you're doing, but it sounds like you want to use some kind of weighted average. Given three quantities $x,y,z$, their weighted average with respective weights $a,b,c$ would be $\dfrac{ax+by+zc}{a+b+c}$. Often it is convenient (and always possible) to choose weights whose sum is $1$, so that the denominator vanishes, but that's not important. In your case, if you want to give $x$ twice as much weight as $y$, and say for example give $y$ and $z$ the same weight, then it would be $\dfrac{2x+y+z}{4}$.


Your Answer

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

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