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.

  • 1
    $\begingroup$ Apparently $k$ is some fixed value. For each value of $i$ in the set $\{1,2,\ldots,Ncm\}$ you’re to choose the largest of the $k-i+1$ fractions $$\frac{n_{ii}}{n_i},\frac{n_{i,i+1}}{n_i},\frac{n_{i,i+2}}{n_i},\ldots,\frac{n_{ik}}{n_i}\;;$$ the value of the expression is the sum of these choices. Without more context that’s all I can tell you. $\endgroup$ – Brian M. Scott May 14 '16 at 15:02
  • $\begingroup$ Thanks Brian for the answer. I really appreciate your response. I have added context of the formula in the question. What I have been trying to do is first understand this formula and then implement this into R. But being new to understanding both at these, I am finding little difficult to comprehend. Can you also please guide me how can implement it into R? $\endgroup$ – tushersuvro May 14 '16 at 17:31
  • $\begingroup$ I was trying to understand the explanation that you gave but still I am having difficulty. Can you give a simple implementation level example? Thanks. $\endgroup$ – tushersuvro Jul 28 '16 at 22:31

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}$$


$$\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$.


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.