Re: [igraph] Re: Question about community detection

[Gábor Csárdi]

On Mon, Dec 21, 2009 at 4:01 PM, zhengjun chen <address@hidden> wrote:
> 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"

Surely can, this means that while making a split, the eigenvector is
computed correctly. Give a higher limit for the number of iterations.

G.

> 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 <address@hidden>
>> 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 <address@hidden>
>> >> 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 <address@hidden
>> >
>> >> >> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM