Re: [igraph] Re: Question about community detection

[zhengjun chen]

What I am most concerned is that why some communities just contain one node.

The Igraph program is correct,and it can handle my dataset.

Is there anything possible wrong? 

Can the warning message from arpack effect the result?

"Warning: Maximum number of ARPACK iterations reached in file community.c, line 1176"

On Mon, Dec 21, 2009 at 9:50 AM, Gábor Csárdi <address@hidden> wrote:

You mean for calculating the optimal division in terms of modularity?
No, this is practically impossible to do.
(http://arxiv.org/abs/physics/0608255)

Btw. this calculation is not even implemented in igraph, see
http://www-rcf.usc.edu/~dkempe/publications/modularity.pdf for a
method to rewrite modularity maximization in an integer programming
form. This can be easily implemented in a linear programming software
package, e.g. GNU Linear Programming Kit.
But still, it will never terminate on your graph.

G.

On Mon, Dec 21, 2009 at 3:33 PM, zhengjun chen <zhjchen.sa@gmail.com> wrote:
> My dataset contain 12,000 nodes. Can Igraph handle it?
>
> On Mon, Dec 21, 2009 at 6:42 AM, Gábor Csárdi <address@hidden> wrote:
>>
>> On Mon, Dec 21, 2009 at 3:01 AM, zhengjun chen <zhjchen.sa@gmail.com>
>> wrote:
>> > Hi,
>> > I choose the community division with highest modularity value. What I
>> > find
>> > is that some communities just contain one node.
>> > So, I am wondering it is a good community division or not. So, is there
>> > any
>> > other way to demonstrate the community division is good or not?
>>
>> I don't know of any. Theoretically it is possible to calculate the
>> best possible division in terms of modularity, but this is not
>> feasible for large graphs.
>>
>> Btw. for me the other methods gave better modularity values on all the
>> graphs i have tried, so you might want to try them. They are also more
>> stable.
>>
>> Gabor
>>
>> > On Sun, Dec 20, 2009 at 10:40 AM, Gábor Csárdi <address@hidden>
>> > wrote:
>> >>
>> >> On Sun, Dec 20, 2009 at 4:26 PM, zhengjun chen <zhjchen.sa@gmail.com>
>> >> wrote:
>> >> > Hi,
>> >> > I am using Modularity to evaluate the goodness of community division.
>> >> > In order to get the largest modularity, a while loop is used to
>> >> > record
>> >> > the
>> >> > modularity value of different "step", which is a parameter of
>> >> > function
>> >> > "igraph_community_leading_eigenvector()". In such way, I record 100
>> >> > modularity value, and find the largest one corresponding to the
>> >> > "step"
>> >> > value
>> >> > 48. I initialized the membership vector and arpack option parameters
>> >> > for
>> >> > every loop.
>> >> > However, to verify the result, I set the "step" to 48, and rerun the
>> >> > program
>> >> > (just one time). The modularity value I get this time is different
>> >> > from
>> >> > that
>> >> > obtained by the while loop. I am a bit confused.
>> >>
>> >> Hi,
>> >>
>> >> one possible explanation is that the eigenvector solver is quite
>> >> unstable, and might result different splits. But it is fine to run it
>> >> a couple of times and then keep the version with the highest
>> >> modularity.
>> >>
>> >> Gabor
>> >>
>> >> > On Sat, Dec 19, 2009 at 5:13 PM, zhengjun chen <zhjchen.sa@gmail.com>
>> >> > wrote:
>> >> >>
>> >> >> Hi,
>> >> >> I have a question about community detection in
>> >> >> Igraph."igraph_community_leading_eigenvector()" function is used to
>> >> >> detect
>> >> >> communities.
>> >> >> My question is what is the meaning of "steps" in this function. Does
>> >> >> it
>> >> >> mean the number of community split operation?
>> >> >> When I change this value from 10 to 100, more and more communities
>> >> >> have
>> >> >> been detected. So, the parameter "steps" should be set to what?
>> >> >> In addition, I have no idea about how many communities actually
>> >> >> exist.
>> >> >> So,
>> >> >> what can I do to verify that the communities detected is good
>> >> >> enough?
>> >> >> I am also a bit confused of the structure igraph_arpack_options_t.
>> >> >> Now
>> >> >> I
>> >> >> just initialize it to default values.
>> >> >>
>> >> >> --
>> >> >> Thanks
>> >> >> zhengjun
>> >> >>
>> >> >> Graduate research assistant
>> >> >> Dept of Computer Science and Engineering
>> >> >> Lehigh University
>> >> >
>> >> >
>> >> >
>> >> > --
>> >> > Thanks
>> >> > zhengjun
>> >> >
>> >> > Graduate research assistant
>> >> > Dept of Computer Science and Engineering
>> >> > Lehigh University
>> >> >
>> >> > _______________________________________________
>> >> > igraph-help mailing list
>> >> > address@hidden
>> >> > http://lists.nongnu.org/mailman/listinfo/igraph-help
>> >> >
>> >> >
>> >>
>> >>
>> >>
>> >> --
>> >> Gabor Csardi <address@hidden>     UNIL DGM
>> >>
>> >>
>> >> _______________________________________________
>> >> igraph-help mailing list
>> >> address@hidden
>> >> http://lists.nongnu.org/mailman/listinfo/igraph-help
>> >
>> >
>> >
>> > --
>> > Thanks
>> > zhengjun
>> >
>> > Graduate research assistant
>> > Dept of Computer Science and Engineering
>> > Lehigh University
>> >
>> > _______________________________________________
>> > igraph-help mailing list
>> > address@hidden
>> > http://lists.nongnu.org/mailman/listinfo/igraph-help
>> >
>> >
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     UNIL DGM
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> --
> Thanks
> zhengjun
>
> Graduate research assistant
> Dept of Computer Science and Engineering
> Lehigh University
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



--
Gabor Csardi <address@hidden>     UNIL DGM


_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help

--
Thanks
zhengjun

Graduate research assistant
Dept of Computer Science and Engineering
Lehigh University