Re: [igraph] Re: Question about community detection

[Gábor Csárdi]

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 <address@hidden>
>> >> > 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