Force based dimension reduction for community detection and display

[Timmy Wilson]

Hi,

I'm interested in reducing a large directed graph to 2-dimensions (for
community detection, similarity queries, and display)

The paper 'Distributed Social Graph Embedding' accurately reflects my
intentions -- hal.inria.fr/inria-00495250/PDF/RR-7327.pdf

The paper highlights 2 forced-based graph embedding methods:

- Noack's LinLog -- http://www.informatik.tu-cottbus.de/~an/GD/

- And something related to Hooke spring attraction

I found networkx's spring_layout which "Positions nodes using
Fruchterman-Reingold force-directed algorithm."

I have 2 questions:

1. Is anyone using spring_layout for community detection?

2. Assuming (hoping for) a positive answer to question 1, would this
algo be easy to distribute (parallelize)?

Thanks,
Timmy Wilson
Cleveland, OH

[Timmy Wilson]

The guys @ gephi have an insightful paper on this topic:

'ForceAtlas2, A Graph Layout Algorithm for Handy Network Visualization'

webatlas.fr/tempshare/ForceAtlas2_Paper.pdf

Any interest in porting Noack's LinLog java implementation?

http://code.google.com/p/linloglayout/

[Aric Hagberg]

On Tue, Dec 6, 2011 at 1:09 PM, Timmy Wilson <tim...@smarttypes.org> wrote:
> The guys @ gephi have an insightful paper on this topic:
>
> 'ForceAtlas2, A Graph Layout Algorithm for Handy Network Visualization'
>
> webatlas.fr/tempshare/ForceAtlas2_Paper.pdf

> Any interest in porting Noack's LinLog java implementation?
>
> http://code.google.com/p/linloglayout/

It might not be hard to modify/update the existing
Fruchterman-Reingold layout code to include these other variants of
force-based layouts.

But what would really go great with that would be to implement a
multiscale method (fast multi-pole, etc) to make it more efficient (n
log(n) instead of n^2).

Aric

[Timmy Wilson]

> But what would really go great with that would be to implement a
> multiscale method (fast multi-pole, etc) to make it more efficient (n
> log(n) instead of n^2).
>
> Aric

I've been researching a few different non-linear dimension reduction
methods (ie -- manifold learning methods --
http://en.wikipedia.org/wiki/Nonlinear_dimensionality_reduction)

I haven't figured it out precisely, but it seems adding a
reconstruction error objective function would let us auto-tweak the
attractive and repulsive forces.

Run the layout code until the energy stabilizes (as normal), then run
a reconstruction error objective function to see how well the final
positions and net of all movement approximate the original graph --
i'm not exactly sure how this would work -- just brainstorming.

Something like an autoencoder, except the forces would be constant, or
close to constant (unlike the weights of an autoencoder).

As for performance, the paper "Distributed Social Graph Embedding"
makes a nice point:

"The importance of locality in these algorithms makes them good
candidates for distribution"

> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
>

[António José Rosas]

Hi everyone,


I am doing link analysis with Networkx and I am dealing with a very common issue related to link analysis: I have several pages from one site and i would like to aggregate them under their main page if present, or simply delete them, if not. If the main page is present, I want to discarding them but only after using them to update the site measures. I imagine that this is possible, but is it feasible? Could you help me on this?


Just an example:

http://www.justlincolnshire.org.uk/index.php/race/

http://www.justlincolnshire.org.uk/

I need to dele the first and update the second (connections, for instance, because the first may be connected or be connected by a new node).

Thank you.

Best,
António

[franck kalala]

Hey Folk,

I have the following:

>>> from networkx import *

>>> G.add_node(1,age=10)

>>> G.add_node(2,age=30)

>>> G.add_edge(1,2)

>>> write_edgelist(G, 'folk.txt')  

how to include the node attributes in the last command?

F

[Aric Hagberg]

It's not possible with the edgelist format. But you can use e.g. GML
or GraphML formats:

import sys
from networkx import *
G=nx.Graph()
G.add_node(1,age=10)
G.add_node(2,age=30)
G.add_edge(1,2)
write_gml(G, sys.stdout)
write_graphml(G, sys.stdout)

Aric

[franck kalala]

THanks Aric,

F

---

De : Aric Hagberg <aric.h...@gmail.com>
À : networkx...@googlegroups.com
Envoyé le : Jeudi 22 Décembre 2011 4h02
Objet : Re: [networkx-discuss] write_edgelist with node attributes.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.

To unsubscribe from this group, send email to networkx-discuss+unsub...@googlegroups.com.