Open questions for network-analysis related modules

[makkus]

This thread collects open questions related to network-analysis that have come up so far, and can't be answered until we analyzed the requirements that come out of the currently ongoing data and workflow collection.

One comment per question.

[makkus]

How should we treat incoming network data by default? Since network data can be interpreted in different ways (directed, undirected, multi-XXX, ...) we can't just assume one way or the other. Depending on the question that needs answering, or the data itself, only a specific network graph type make sense. Should we include this with the actual data?

[yaslena]

This is a variation of the question I.1 in the workflow requirements discussion:
DHARPA-Project/DHARPA-Project-workflows-requirements#1 (comment)

There is no easy answer. Directed multigraphs have more information than directed graphs. And directed graphs contain more information than undirected graphs. To avoid potential information loss, we could go for the graph type that would be able to capture most of the information in the data. Depending on the question ((information-)flow, dependencies, provenance ... vs. affiliations, memberships, co-occurence ...) only directed or undirected graphs would make sense.

[makkus]

Right, I think this makes sense, and we just 'down-cast' graph data to lower-information content types on demand. I think we'll need to play around with how users would interact with all of this, and our example workflows will hopefully help with that. But I can imagine that our 'network_data' would just serve as the basis for us to create the right kind of graph 'on-demand', getting rid of unnecessary information on a case-by-case basis (like directions), depending on the research question or module inputs necessary.

That comes back to the question about 'data-qualities', I guess. It looks like that the network data we store will be in most cases be 'qualified' when actually used (e.g. cast into a specific network graph type), and that qualified data is then used as input. One thing we should not forget is document exactly what information gets lost when we do that, and how the transformation is done (for example, when merging multiple edges into one and adding up their weights -- this would produce a different graph as when we would just ignore duplicated edges, but only if weight is involved).

[makkus]

In our edges table, if we name our columns 'source' and 'target', we point towards a directed graph, even if that is not the case. How should we handle that, should we pick more generic names (node1, node2)?

[yaslena]

I would not change established terminology, even if it is confusing in this case. Many algorithms like shortest path and graph traversal can be used for both directed and undirected graphs and would have to be rewritten if the terminology was changed. I have also found this resoning on the GML documentation page:
"There are two reasons why we did not define separate representations for directed and undirected graphs. First, it would have made the parser more complex, especially in applications that read both directed and undirected graphs. Second, if graphics get involved, source and target have a meaning even for undirected graphs: if an edge is represented by a polyline, then the sequence of points implies a direction on the edge." (http://openmis.ru/doc/clang/gml-tr.html)

[makkus]

Makes sense, this is good information. I'll make sure to include this in the documentation that is associated with the 'network_data' value type and explain the reasoning behind some of the characteristics of that type, so users can look this up if the question comes up (or if they just want to be aware of all potential pitfalls related to that type).