Re: [igraph] Working with large networks and how to sample from a graph?

[Gábor Csárdi]

On Thu, Apr 5, 2012 at 7:40 AM, Peter Flom
<address@hidden> wrote:
> Thanks Tamas
>
> That brings up a suggestion - in the next version of the manual it would be
> nice to see, for each measure, a rough idea of running time. Obviously, this
> couldn't be precise as it depends on the machine running the code and
> probably on lots of other things, but something indicating that betweenness
> centrality running time is proportional to links*nodes, whereas degree seems
> to be linear in nodes (from what I can tell) and similar for other measures.

You are right, this should be in the manual. It is included in the C
manual for most functions:
http://igraph.sourceforge.net/doc/html/index.html
and the R running time complexity is almost always the same.
Betweenness is O(nm), the number of nodes times the number of edges:
http://igraph.sourceforge.net/doc/html/igraph_betweenness.html

Gabor

> Thanks again
>
> Peter Flom
> Peter Flom Consulting
> http://www.statisticalanalysisconsulting.com/
> http://www.IAmLearningDisabled.com
>
> -----Original Message-----
> From: address@hidden
> [mailto:address@hidden
> On Behalf Of Tamás Nepusz
> Sent: Thursday, April 05, 2012 7:35 AM
> To: Help for igraph users
> Subject: Re: [igraph] Working with large networks and how to sample from a
> graph?
>
>> > Thanks
>> >
>> > These big networks are hard! My past experience is with networks of
>> > a couple hundred nodes, at most
>> >
> Another thing you might want to think about is whether you really need the
> betweenness centrality of the nodes or it is enough to use _any_ sensible
> centrality measure. For instance, eigenvector centrality and PageRank can be
> calculated way faster than betweenness centrality or closeness centrality on
> large networks.
>
> T.
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI