Firstly, apologies needed for my math description if it does not sound right.
I have come across a paper where I saw a summation notation with a max function in it which I am little confused to understand. The formula is as follows:
$$\sum_{i=1}^{Ncm}\max_{i\le j\le k}\left\{\frac{n_{ij}}{n_i}\right\}$$
The context of the above formula – It is a purity function and it is used to evaluate whether the quality of detection of communities is good. You can know more from Here
Here, $N_{cm}$ represents the number of detected communities, $n_{ij}$ refers to the number of nodes belonging to topic j and community i, $n_{i}$ refers to the number of nodes in community i. k is the number of topics in the network.
Now, can anyone please guide me thorough about how can I break this notation with numbers and understand it correctly. Thanks.
Best Answer
As requested, here’s a concrete example; I have no idea whether the numbers are at all plausible, but they at least illustrate the computation.
First let me correct the expression; it’s
$$Purity=\frac1{N_{cm}}\sum_{i=1}^{N_{cm}}\max_{1\le j\le K}\frac{n_{ij}}{n_i}\;,$$
where $N_{cm}$ is the number of communities, $n_{ij}$ is the number of nodes belonging to topic $j$ and community $i$, and $n_i$ is the number of members in community $i$. $K$ is the number of topics.
Suppose that $K=3$, so that there are three topics, and the algorithm detects $N_{cm}=2$ communities, which I’ll call $C_1$ and $C_2$. Suppose that $C_1$ has $n_1=4$ members, and $C_2$ has $n_2=7$ members. Finally, suppose that the numbers $n_{ij}$ are given by the following array:
$$\begin{array}{c|cc} i\backslash j&1&2&3\\ \hline 1&0&2&3\\ 2&7&2&1 \end{array}$$
Then
$$\begin{align*} \sum_{i=1}^2\max_{1\le j\le 3}\frac{n_{ij}}{n_i}&=\max_{1\le j\le 3}\frac{n_{1j}}4+\max_{1\le j\le 3}\frac{n_{2j}}7\\ &=\max\left\{\frac{n_{11}}4,\frac{n_{12}}4,\frac{n_{13}}4\right\}+\max\left\{\frac{n_{21}}7,\frac{n_{22}}7,\frac{n_{23}}7\right\}\\ &=\frac14\max\{n_{11},n_{12},n_{13}\}+\frac17\max\{n_{21},n_{22},n_{23}\}\\ &=\frac14\max\{0,2,3\}+\frac17\max\{7,2,1\}\\ &=\frac34+\frac77\\ &=\frac74\;, \end{align*}$$
and $Purity=\frac12\cdot\frac74=\frac78$.