Ontology for Graph Theory

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Ontology for Graph Theory

Masa
Hello,

I'm looking for an ontology for Graph Theory.
Does anyone know any ontology about Graph Theory?
I'm thinking to develop a Question Answering System which can answer
graph problems (such as Shortest Path, Minimum Spanning Tree, Betweenness Centrality, etc.).

Regards,
Masa

_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Maxim Veksler
I'm interested in how you envision this working ?

Being new to Semantic Web I haven't seen graph traversal being a common
practice in SPARQL based triple stores.

Could you articulate please how you view this going forward?



--
Sent from: http://protege-project.136.n4.nabble.com/Protege-User-f4659818.html
_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Michael DeBellis-2
In reply to this post by Masa
Masahiro, Have you found any usable ontologies for this? If not I would be interested in working with you to create one. If I'm understanding what you are looking for I think creating such an ontology would be relatively easy (famous last words). If you are interested please contact me directly at [hidden email]  

Michael

On Tue, Nov 13, 2018 at 2:56 PM Masahiro Hayakawa <[hidden email]> wrote:
Hello,

I'm looking for an ontology for Graph Theory.
Does anyone know any ontology about Graph Theory?
I'm thinking to develop a Question Answering System which can answer
graph problems (such as Shortest Path, Minimum Spanning Tree, Betweenness Centrality, etc.).

Regards,
Masa

_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user

_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Alex Shkotin
In reply to this post by Masa
Dear Masa,

it's definitely a great topic but not very "ontological". You may change from "ontology" to axiomatic theory and it's models for ex. just finite graphs.
I am sure systems like Coq or Wolfram Alpha have a lot for you. XOR would you like to make the task on OWL2,  CASL, CL... Wich language do you prefer in this case?

Actually, there are two theories: for directed and undirected graphs...

Anyway, please, keep in touch as I have in my working area the beginning of axiomatic graph theory (2 of them) not ready to publish and some discussion here in Russian but you know google-trans I hope :-) 

Alex

ср, 14 нояб. 2018 г. в 01:56, Masahiro Hayakawa <[hidden email]>:
Hello,

I'm looking for an ontology for Graph Theory.
Does anyone know any ontology about Graph Theory?
I'm thinking to develop a Question Answering System which can answer
graph problems (such as Shortest Path, Minimum Spanning Tree, Betweenness Centrality, etc.).

Regards,
Masa

_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user

_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Masa
In reply to this post by Maxim Veksler
Hi Maxim,

> Could you articulate please how you view this going forward?
>
For example, to solve a shortest path, we need source node and target node.
Humans knows that, but machines don't. So, to fill the gap between humans
and machines in terms of QA system, background knowledge is required.
And I guess an ontology can play the role.

Masa



--
Sent from: http://protege-project.136.n4.nabble.com/Protege-User-f4659818.html
_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Masa
In reply to this post by Michael DeBellis-2
Hi Michael,

> Masahiro, Have you found any usable ontologies for this?
>
No, I've not found yet.

> If not I would be interested in working with you to create one.
>
Thank you for having an interest in my activity.

> I think creating such an ontology would be relatively easy.
>
Yes, it might be easy.
But before creating the one, I just want to know if such ontologies exist or
not.

Masa



--
Sent from: http://protege-project.136.n4.nabble.com/Protege-User-f4659818.html
_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Masa
In reply to this post by Alex Shkotin
Dear Alex,

> would you like to make the task on OWL2,  CASL, CL...
> Wich language do you prefer in this case?
>
If I cannot find any ontology about graph theory, then I would create it,
maybe in OWL2.

> I have in my working area the beginning of axiomatic graph theory
>
I heard the term "Axiomatic Graph Theory" for the first time.
And I don't know the difference between "Axiomatic Graph Theory" and "Graph
Theory".

Anyway, what I want to do with an ontology is like below.
1) Share the concept of graph theory with machines.
2) Prepare vocabulary to describe graph problems.

After identifying user's intention, the system will solve
the graph problem by using graph algorithm APIs.


Masa



--
Sent from: http://protege-project.136.n4.nabble.com/Protege-User-f4659818.html
_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Alex Shkotin
Hi Masa,

may be I should say Formal Axiomatic Theory of Graphs :-)
Where we have axiom like this (e:E 1(#v:V inc(e v))≤2) see here and we have formal definitions and formal proofs. In this case any particular graph is a finite model of this axiom.
1) They say to "Share the concept of graph theory with machines" we need more powerful language than OWL2 - may be Coq. 
2) "Prepare vocabulary to describe graph problems" does it mean to give formal definitions for such concept as " Shortest Path, Minimum Spanning Tree, Betweenness Centrality" etc?

To keep graph in ontology we need 2 classes: Edge, Vertex and one object property - incident (e1 inc v1), see in axiom above where "#" means "number of", i.e. number of vertex being incident to any edge is more than 0 and less than 3. It seems this axiom may be written on OWL2/DL. 
Then we need axiom that Edge and Vertex are disjoint.

Is this your direction?

Alex

чт, 29 нояб. 2018 г. в 09:23, Masa <[hidden email]>:
Dear Alex,

> would you like to make the task on OWL2,  CASL, CL...
> Wich language do you prefer in this case?
>
If I cannot find any ontology about graph theory, then I would create it,
maybe in OWL2.

> I have in my working area the beginning of axiomatic graph theory
>
I heard the term "Axiomatic Graph Theory" for the first time.
And I don't know the difference between "Axiomatic Graph Theory" and "Graph
Theory".

Anyway, what I want to do with an ontology is like below.
1) Share the concept of graph theory with machines.
2) Prepare vocabulary to describe graph problems.

After identifying user's intention, the system will solve
the graph problem by using graph algorithm APIs.


Masa



--
Sent from: http://protege-project.136.n4.nabble.com/Protege-User-f4659818.html
_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user

_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user
Reply | Threaded
Open this post in threaded view
|

Re: Ontology for Graph Theory

Michael DeBellis-2
In reply to this post by Masa
Masa, Here is a basic graph theory ontology. This is really quick and dirty, there is a lot more that could be done but it has Graphs, Nodes, Edges, records which edges connect to and from each node, the cost of the edge, associates edges and nodes with a graph, finds successors for a node, etc. A lot of the reasoning is done automatically by inverse and transitive properties and some simple SWRL rules. I'm including a PDF of the simple tree graph I used for my example as well as the ontology. If you have questions or specific things you are looking for and want to expand this please let me know. 

Michael

On Wed, Nov 28, 2018 at 10:23 PM Masa <[hidden email]> wrote:
Dear Alex,

> would you like to make the task on OWL2,  CASL, CL...
> Wich language do you prefer in this case?
>
If I cannot find any ontology about graph theory, then I would create it,
maybe in OWL2.

> I have in my working area the beginning of axiomatic graph theory
>
I heard the term "Axiomatic Graph Theory" for the first time.
And I don't know the difference between "Axiomatic Graph Theory" and "Graph
Theory".

Anyway, what I want to do with an ontology is like below.
1) Share the concept of graph theory with machines.
2) Prepare vocabulary to describe graph problems.

After identifying user's intention, the system will solve
the graph problem by using graph algorithm APIs.


Masa



--
Sent from: http://protege-project.136.n4.nabble.com/Protege-User-f4659818.html
_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user

_______________________________________________
protege-user mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-user

GraphTheoryOntology.owl (33K) Download Attachment
Graph1.pdf (51K) Download Attachment