1

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.

tushersuvro
  • 29
  • 1
    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.

     – Brian M. Scott May 14 '16 at 15:02
  • 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? – tushersuvro May 14 '16 at 17:31
  • 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. – tushersuvro Jul 28 '16 at 22:31

1 Answers1

1

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

Brian M. Scott
  • 616,228