Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Eclipse Projects » Spatiotemporal Epidemiological Modeler (STEM) » New Types of Graphs(New Types of Graphs)
New Types of Graphs [message #513686] Wed, 10 February 2010 19:48 Go to next message
James Kaufman is currently offline James KaufmanFriend
Messages: 167
Registered: July 2009
Senior Member
In todays call we discussed the need for new types of graphs in STEM.
Suggestions included
1. Ability to Model on Lattices
2. Addition of a better map of Europe
3. How to maintain and expose a variety of maps in the designer perspective
4. How to free STEM of the requirement that we have a fixed set of polygons. We want to visualize maps but we could, for example, define a higher resolution map of Europe without polygons and just draw cricles.
5. Other Tesselations of the world

1) Regarding lattices, STEM already has a little button on top of the menu bar that looks like a lattice with nodes and edges. This is the create graph button and right now it launches a wizard that creates and empty graph (all you can do is name it). You can try this button today. Ideally when you press the button the wizard should allow the user some options one of which would be square lattice with a way to specify number of rows and edges. This will then appear in the project explorer and it can be dragged into a users project.

2) The big issue with a better map of Europe is finding data available with an EPL friendly license. We are working in this.
3) Suggestions? Using the new graph button we can in principle enable a variety of graph creation algorithms programatically (not just lattices but also tesselations)
4) Suggestions?
5) See 3 above.

Re: New Types of Graphs [message #515296 is a reply to message #513686] Thu, 18 February 2010 12:02 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
Concerning the first issue:

I would appreciate such a feature very much as well. What one could consider additionally is whether this would be a way to incorporate and simulate on other network structures as well. I could imagine that one gives the user the opportunity to upload a file in a defined format, e.g. a DyNetML or other usual file formats in network analysis.
What is still not clear to me is the question, whether a user could then in principle combine this proprietary graph from his workspace with the ones that come with the installation? If this would be possible, I guess some of the other issues raised in this news thread can be solved as well.

Matthias
Re: New Types of Graphs [message #539333 is a reply to message #513686] Thu, 10 June 2010 13:09 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
As discussed on the weekly conference call yesterday here those newsgroup pieces that refer to the "import arbitrary network structures" issue:

1.: network file formats:
http://netwiki.amath.unc.edu/DataFormats/Formats
=> I personally would prefer the Pajek ".net" format

2.: nodes without GIS information:
... There are situations, where users don't want to locate the node site on a map, because this would cause problems with data privacy, e.g. a farm or a hospital etc.. So the question is whether it is much effort to open the system for data without GIS information, i.e. arbitrary placing nodes into existing country maps. So if this (nodes without GIS) would be possible then one could also extend the STEM functionality with features from the graph theory community that can help to descibe the network used in a simulation, e.g. distribution of the indegrees or outdegrees of nodes etc.. http://en.wikipedia.org/wiki/Centrality

I will post a sample file asap.

3.: graphical editors:
Library that might be of interest: http://jung.sourceforge.net/ and that is also compatible with the pajek ".net"-format.
Re: New Types of Graphs [message #539466 is a reply to message #539333] Thu, 10 June 2010 20:44 Go to previous messageGo to next message
Stefan Edlund is currently offline Stefan EdlundFriend
Messages: 127
Registered: July 2009
Location: IBM
Senior Member
Just a comment on the "minimal" functionality I think a graph format should have.

1. "Node ID". So we can identify nodes. We can generate the URI we use inside STEM from the ID. I strongly suggest that Node IDs are unique (but it's not strictly necessary).

2. Edge with two Node IDs to connect.

3. One or more node attribute name and value

If we only have this, we would assume the following:

1. A node is a location
2. An edge is a mixing edge (i.e. neighboring nodes)
3. In the node attribute name, we would need to encode some extra information. E.g. "population_human" is for human population data, "population_deer" is deers etc. The value is always assumed double

That's the absolute minimum. It would be very nice to also have this:

1. One or more edge attribute names and values.

This way we can represent flows, like passengers/day. An edge attribute named 'type' could be used to distinguish between mixing edges, migration edges and physical containment edges. Another attribute 'direction' indicates unidirectional or bidirectional.

That's the smallest functionality I can think of. It would of course be nice to have additional semantics such as attribute types, node types and edge types.

Observe that an edge can connect to a Node ID that is not found inside the file. It might be imported later from another file. STEM resolves and reports any dangling edges before starting a simulation.

- Stefan





Re: New Types of Graphs [message #539544 is a reply to message #539466] Fri, 11 June 2010 08:52 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
I think the Pajek ".net" format gives us all the flexibility you mentioned we need. In case of the vertice (node) attributes we would have to define a STEM-specific grammar with which we would extend the one from Pajek. For the details see pages 71 to 74 of the Pajek manual: http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf

For a node (vertice in Pajek) the following notation is defined:
vertex-num label [x y z] [shape] [changes of default parameters]

We could use all the fields and if we extend the "label" field with a STEM grammar we could as well integrate STEM specific informations. This is possible as with Pajek one can use labels that consist of more then one word as long as these are enclosed in pair of special characters (e.g., "vertex 1").
So we could define the following STEM specific label-notation:
"name= STEM_nodeName, [pop-value= number, pop-type= population-name], [node-area= area-used-in-calculation], [node-size= factor-used-when-displayed], etc."

The same should work for *Arcs (directed connections between nodes) or Edges (undirected connections).
vertex-num1 vertex-num2 value [additional parameters]

(here the parameter "l "- (line label) gives us the option to insert STEM specific informations if necessary.

Additionally on the Pajek website there are tools available that transform ".txt" or ".csv" formatted files into the Pajek (.net) format, so we dont have to care about this much.

Matthias

Re: New Types of Graphs [message #540250 is a reply to message #539544] Tue, 15 June 2010 13:27 Go to previous messageGo to next message
Arik Kershenbaum is currently offline Arik KershenbaumFriend
Messages: 13
Registered: January 2010
Location: Israel
Junior Member
Are we looking for a generic framework that will replace all our properties files (area, node, centers, names), and also the map.xmls? If we're going to incorporate a graph generator for arbitrary graphs, then integrating the map xml to the network representation seems important. Border length, for instance, may determine the strength of an arc.


==============
Arik Kershenbaum
Prof Blaustein's laboratory
Department of Evolutionary and Environmental Biology
University of Haifa
http://research.haifa.ac.il/~leon/html/Arik_Page.htm
Re: New Types of Graphs [message #540302 is a reply to message #540250] Tue, 15 June 2010 15:00 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
This is really a good question. I think the map.xml information is probably something that we can not place into the Pajek format. I could imagine to create a specific label notation where a user gives the name of the map.xml-file so that this information can be associated to the correct node. Concerning the border length - as far as I understood - this is in the end just a number. It could be specified by the user them self without any problems if he wants to use this information within the simulation. If it is not given then it might be calculated from the XML-file, but this should be specifically demanded by the user, otherwise the user might wonder why the simulation give strange results if he is not aware of that procedure. To make it clear: I would prefer a system where no transportation information is implicitly used within a simulation. If a user thinks that the border length is representative for population member exchange between neighbouring nodes then he should place that (property) graph into the model. If he thinks the number of roads are relevant then the same applies. And if neither roads or border lenght is relevant (e.g. in cases of animal transportation) then he should be able to integrate his own traffic numbers into his model.

BTW: another issue came to my mind where it is necessary to agree on a specific notation, e.g. for bird migration models. There you might have transport processes at specific time points during the simulation. So in order to incorporate all relevant model information a user must be able to assign information on time to the transport information (e.g. on the number of population members that moved from one node to another).
This should be possible again to be covered with a specific label notation in the Pajek format.
Re: New Types of Graphs [message #540383 is a reply to message #513686] Tue, 15 June 2010 22:59 Go to previous messageGo to next message
Stefan Edlund is currently offline Stefan EdlundFriend
Messages: 127
Registered: July 2009
Location: IBM
Senior Member
Arik, I don't think we're trying to replace all the existing .properties and .xml files in STEM, they've served us well in generating the standard libraries available.

I think the idea is to come up with a common graph format that (with as little effort as possible) other graphs formats can be converted to and then imported into STEM when the user is building a new scenario.

Looking into the .pajek format, it seems to be heavily focused on how to visualize networks with commands for fonts, colors, node shapes etc. etc. It even has a free editor/visualizer. There's less focus on node/edge attributes and no type system as far as I can tell. We would need to encode lots of that extra information into the labels, is that right?

/ Stefan
Re: New Types of Graphs [message #540430 is a reply to message #540383] Wed, 16 June 2010 07:16 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
Yes, that's the way it could work.
Re: New Types of Graphs [message #540681 is a reply to message #540430] Thu, 17 June 2010 00:26 Go to previous messageGo to next message
Stefan Edlund is currently offline Stefan EdlundFriend
Messages: 127
Registered: July 2009
Location: IBM
Senior Member
Ok, in my mind .pajek would be useful if we were just trying to come up with nice visualization of networks. I'd rather see a format that makes node/edge attributes and values first-class objects instead of forcing us to come up with our own internal representations.

Not sure what the alternatives are, but the links you posted below helps.

Regards,
/ Stefan
Re: New Types of Graphs [message #541123 is a reply to message #513686] Fri, 18 June 2010 12:33 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
I think in the end this discussion leads to the conclusion that we have to define a generic (XML) format for epidemiological models. I searched quite a while on the web and discussed it with external experts but no-one new about an existing standard. What I found was the following:
http:// docs.epigrass.metamodellers.com/using.html#specifying-a-mode l-the-script
BTW - Epigrass seems to be quite close to what STEM is doing, just with a different programming language.

Anyway, I think, to generate a new standard is probably something that takes some time and that should be guided by someone who has experience in this. I guess, there are for sure experts in the eclipse community for this. Independent from this we need an interim standard, so that the different developments in STEM can continue. Imho, this should be defined in the near future.

Regards,

Matthias
Re: New Types of Graphs [message #541522 is a reply to message #541123] Mon, 21 June 2010 13:15 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
Just an addendum:
Maybe one could schedule a first interim solution for the network structure import feature for the release 1.1.0 on 18th August 2010? We would try to contribute a solution for a pajek2STEM import function until then.
Re: New Types of Graphs [message #541606 is a reply to message #541522] Mon, 21 June 2010 18:27 Go to previous messageGo to next message
Stefan Edlund is currently offline Stefan EdlundFriend
Messages: 127
Registered: July 2009
Location: IBM
Senior Member
Yes, there is already a feature 317079 created for this in bugzilla with a target milestone of 1.1.0 (it's assigned to you).

/ Stefan
Re: New Types of Graphs [message #563986 is a reply to message #539333] Thu, 10 June 2010 20:44 Go to previous messageGo to next message
Stefan Edlund is currently offline Stefan EdlundFriend
Messages: 127
Registered: July 2009
Location: IBM
Senior Member
Just a comment on the "minimal" functionality I think a graph format should have.

1. "Node ID". So we can identify nodes. We can generate the URI we use inside STEM from the ID. I strongly suggest that Node IDs are unique (but it's not strictly necessary).

2. Edge with two Node IDs to connect.

3. One or more node attribute name and value

If we only have this, we would assume the following:

1. A node is a location
2. An edge is a mixing edge (i.e. neighboring nodes)
3. In the node attribute name, we would need to encode some extra information. E.g. "population_human" is for human population data, "population_deer" is deers etc. The value is always assumed double

That's the absolute minimum. It would be very nice to also have this:

1. One or more edge attribute names and values.

This way we can represent flows, like passengers/day. An edge attribute named 'type' could be used to distinguish between mixing edges, migration edges and physical containment edges. Another attribute 'direction' indicates unidirectional or bidirectional.

That's the smallest functionality I can think of. It would of course be nice to have additional semantics such as attribute types, node types and edge types.

Observe that an edge can connect to a Node ID that is not found inside the file. It might be imported later from another file. STEM resolves and reports any dangling edges before starting a simulation.

- Stefan
Re: New Types of Graphs [message #564009 is a reply to message #563986] Fri, 11 June 2010 08:52 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
I think the Pajek ".net" format gives us all the flexibility you mentioned we need. In case of the vertice (node) attributes we would have to define a STEM-specific grammar with which we would extend the one from Pajek. For the details see pages 71 to 74 of the Pajek manual: http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.p df

For a node (vertice in Pajek) the following notation is defined:
vertex-num label [x y z] [shape] [changes of default parameters]

We could use all the fields and if we extend the "label" field with a STEM grammar we could as well integrate STEM specific informations. This is possible as with Pajek one can use labels that consist of more then one word as long as these are enclosed in pair of special characters (e.g., "vertex 1").
So we could define the following STEM specific label-notation:
"name= STEM_nodeName, [pop-value= number, pop-type= population-name], [node-area= area-used-in-calculation], [node-size= factor-used-when-displayed], etc."

The same should work for *Arcs (directed connections between nodes) or Edges (undirected connections).
vertex-num1 vertex-num2 value [additional parameters]

(here the parameter "l "- (line label) gives us the option to insert STEM specific informations if necessary.

Additionally on the Pajek website there are tools available that transform ".txt" or ".csv" formatted files into the Pajek (.net) format, so we dont have to care about this much.

Matthias
Re: New Types of Graphs [message #564030 is a reply to message #564009] Tue, 15 June 2010 13:27 Go to previous messageGo to next message
Arik Kershenbaum is currently offline Arik KershenbaumFriend
Messages: 13
Registered: January 2010
Location: Israel
Junior Member
Are we looking for a generic framework that will replace all our properties files (area, node, centers, names), and also the map.xmls? If we're going to incorporate a graph generator for arbitrary graphs, then integrating the map xml to the network representation seems important. Border length, for instance, may determine the strength of an arc.

--

==============
Arik Kershenbaum
Prof Blaustein's laboratory
Department of Evolutionary and Environmental Biology
University of Haifa
http://research.haifa.ac.il/~leon/html/Arik_Page.htm


==============
Arik Kershenbaum
Prof Blaustein's laboratory
Department of Evolutionary and Environmental Biology
University of Haifa
http://research.haifa.ac.il/~leon/html/Arik_Page.htm
Re: New Types of Graphs [message #564051 is a reply to message #540250] Tue, 15 June 2010 15:00 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
This is really a good question. I think the map.xml information is probably something that we can not place into the Pajek format. I could imagine to create a specific label notation where a user gives the name of the map.xml-file so that this information can be associated to the correct node. Concerning the border length - as far as I understood - this is in the end just a number. It could be specified by the user them self without any problems if he wants to use this information within the simulation. If it is not given then it might be calculated from the XML-file, but this should be specifically demanded by the user, otherwise the user might wonder why the simulation give strange results if he is not aware of that procedure. To make it clear: I would prefer a system where no transportation information is implicitly used within a simulation. If a user thinks that the border length is representative for population member exchange between neighbouring nodes then he should place that (property) graph into the model. If he thinks the number of roads are relevant then the same applies. And if neither roads or border lenght is relevant (e.g. in cases of animal transportation) then he should be able to integrate his own traffic numbers into his model.

BTW: another issue came to my mind where it is necessary to agree on a specific notation, e.g. for bird migration models. There you might have transport processes at specific time points during the simulation. So in order to incorporate all relevant model information a user must be able to assign information on time to the transport information (e.g. on the number of population members that moved from one node to another).
This should be possible again to be covered with a specific label notation in the Pajek format.
Re: New Types of Graphs [message #564156 is a reply to message #540430] Thu, 17 June 2010 00:26 Go to previous messageGo to next message
Stefan Edlund is currently offline Stefan EdlundFriend
Messages: 127
Registered: July 2009
Location: IBM
Senior Member
Ok, in my mind .pajek would be useful if we were just trying to come up with nice visualization of networks. I'd rather see a format that makes node/edge attributes and values first-class objects instead of forcing us to come up with our own internal representations.

Not sure what the alternatives are, but the links you posted below helps.

Regards,
/ Stefan
Re: New Types of Graphs [message #564185 is a reply to message #541123] Mon, 21 June 2010 13:15 Go to previous messageGo to next message
Matthias Filter is currently offline Matthias FilterFriend
Messages: 74
Registered: July 2009
Member
Just an addendum:
Maybe one could schedule a first interim solution for the network structure import feature for the release 1.1.0 on 18th August 2010? We would try to contribute a solution for a pajek2STEM import function until then.
Re: New Types of Graphs [message #564205 is a reply to message #564185] Mon, 21 June 2010 18:27 Go to previous message
Stefan Edlund is currently offline Stefan EdlundFriend
Messages: 127
Registered: July 2009
Location: IBM
Senior Member
Yes, there is already a feature 317079 created for this in bugzilla with a target milestone of 1.1.0 (it's assigned to you).

/ Stefan
Previous Topic:New Types of Graphs
Next Topic:No data with source code?
Goto Forum:
  


Current Time: Sat Nov 22 10:30:27 GMT 2014

Powered by FUDForum. Page generated in 0.02371 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software