[Networkit] Node Indices NetworKit

Christian Staudt christian.staudt at kit.edu
Thu Jul 9 17:20:52 CEST 2015


Georg, thanks for you feedback.

> Does NetworKit  assign new integer indices to nodes, even if the imported nodes are already integers?

It is necessary for NetworKit that the node ids are consecutive integers. Therefore ids are remapped by some graph file readers if the file format allows arbitrary (integer) ids.

> This is a major issue since individual nodes cannot be interpreted after loading the graph into NetworKit. For example returning the nodes with the highest betweenness centrality are only indices and it's not possible to know which those nodes actually are.

I agree that this is a major issue which we haven’t solved yet. I see the following solution: Any graph reader that performs a mapping between “external” and “internal” node identifiers should have a method to retrieve this mapping.

@Max: Can you build an appropriate solution, possibly collaborating with Georg?

> The output of the community detection differs every time this command is called. I understand that those algorithms are not accurate, but the results differ quite significantly.

The parallel community detection algorithms are nondeterministic, but I would not expect drastically different results. Can you send the commands you use to perform community detection? How do you compare the results?

> Could you tell me which of the methods currently support directed graphs?

Any algorithm that takes a graph should either work correctly on directed graphs or throw a meaningful exception in case it is not defined or not yet implemented for directed graphs. Please report the bug if that is not the case.

Best,
Chris

On 09 Jul 2015, at 14:20, Georg J. Tilch <tilchgeo at wiwi.hu-berlin.de> wrote:

> Hello Christian,
> 
> I want to use NetworKit to analyze different directed and undirected graphs and I am working into your great tool. I have some questions which I couldn't answer going through the documentation.
> 
> 
> Does NetworKit  assign new integer indices to nodes, even if the imported nodes are already integers? If I import for example an edgelist, nodes in NetworKit are consequtive integers (see below), even if those integers don't exist in the input file.
> 
> This is a major issue since individual nodes cannot be interpreted after loading the graph into NetworKit. For example returning the nodes with the highest betweenness centrality are only indices and it's not possible to know which those nodes actually are.
> 
> The same happens if I load a graph where nodes are in fact hashable strings. You write in your documentation that nodes are integer indices, so maybe additional node labels would be great.
> 
> 
> The output of the community detection differs every time this command is called. I understand that those algorithms are not accurate, but the results differ quite significantly.
> 
> 
> Could you tell me which of the methods currently support directed graphs?
> 
> Thank you very much for your support and maybe it helps for the futher development.
> Georg
> 
> 
> PS: Data format and steps taken:
> 
> # Input edgelist: NodeID1 \t NodeID2
>     10000   27699
>     10002   10015
>     ...
> 
> #  Corresponding nodes of the egelist
>     2
>     3
>     4
>     6
>     9
>     12
>     ...
> 
> 
> # Import edgelist
>     G = readGraph("edgelist",Format.EdgeList,separator='\t', firstNode=2,  continuous=False)
> 
> # List of nodes in the graph: G.nodes()
>     [0,
>      1,
>      2,
>      3,
>      4,
>      5,
>      ...
> 
> Note that nodes 0, 1, 5 do not exist in the data...
> 
> 
> 
> --
> Cell: +49 160 8133442
> Fax: +49 322 23399886
> E-mail: tilchgeo at wiwi.hu-berlin.de
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150709/d8e73946/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150709/d8e73946/attachment.sig>


More information about the NetworKit mailing list