What is a graph and its types?

First of all, it is necessary to define and understand what a semantic data model is. A semantic data model is a data structuring method that aims to represent certain data in a specific logical way. In this model, basic semantic information is included to the data and the relationships that exist between them. This way of organizing data allows for easy development as well as easy maintenance when updating certain data.

“The semantic web is not just about putting data on the web. It's about creating links so that a person or a machine can explore the web of data. With linked data, when you have some of it, you can find other related data." - Tim Berners-Lee, father of the World Wide Web and the Semantic Web

The term graph refers to drawing or image and its characteristics allow for enterprise level data analysis and solutions. A graph is a set of objects known as nodes that are related to each other through a set of connections known as edges. Therefore, the use of networks allows the study of the existing relationships between 'things' that interact with each other. A graph is composed of vertices (v) and edges (e) and when we speak of 'Order' we refer to the number of vertices of the graph, as well as when we speak of 'loop' we are referring to an edge related in different ways with the same node. Lastly, the term 'degree' refers to the number of points that affect a vertex. Graphs can be divided into three, as explained below:

• Directed graph:

  This type of graph is also known as 'digraph' because each edge is associated with a node in a single direction through an arrow. Therefore, the edges can receive the term incoming or outgoing depending on their outgoing or incoming, but always with destination to a node.

  

• Undirected graph:

  Unlike directed graphs, this type of graph contains a set of vertices connected to a certain number of edges in a non- directional way. That is, an edge can be traversed from any of its points and in any direction.

• Labeled graph:

  graphs, which are the most used to represent real life situations, contain within it labeled directed graphs and labeled undirected graphs. This type of graphs concentrate edges with additional information such as names, values, etc... and therefore the links between vertices have a weight factor (value) considered as labels.

  

Knowledge Graph

A knowledge graph is a network of descriptions of entities or concepts that show the relationship between them (also known as a semantic network). This type of graphs (which are centralized) are implemented within the domain of a certain organization and are able to collect data from various sources inside or outside the organization, to find information faster, understand it better and apply it together with AI or ML.

That is, Knowledge Graph consists of a directed labeled graph where the labels have very well defined meanings to understand the relationship between nodes. A more technical definition would be given a set of nodes N, and a set of labels E, the KG is the subset of N x E x N. As indicated in some models, if we look at Figure 2 in the labeled directed graph, we could say that A is the subject, label (40) is the predicate and C is the object.

Difference KG and Ontologies

An ontology consists of a semantic data model where the types of things that exist within a domain are defined, that is, generalized data with common properties are modeled, without including specific information about individual things. A 'Computer' would be a generalized model, however 'A Macbook Pro 13' is a specific entity. So it would describe the general characteristics of computers that all computers can have and not those of a Macbook Pro 13. Ontologies have 3 essential components:

• 1. Classes: are the different things that contain our data.
• 2. Relations: is the property or properties that connect two classes.
• 3. Attributes: these are the characteristics that an individual class has.

Let's understand it better with a simple example imagining that we have this information about computers.

Computers	Screen	Processor brand	CPU	Storage	Fingerprint
MacBook Air	13,3 inch	Apple M1	8 Core	Up to 2 TB	Yes
MacBook Pro 14	14,2 inch	Apple M1	10 Core	Up to 8 TB	Yes
MacBook Pro 13	13,3 inch	Intel Core	2 Core	Up to 1 TB	No

Processor brand	Type	Up to i5	Up to i7
Apple M1	Apple M1 Chip
Apple M1	Apple M1 Pro Chip
Apple M1	Apple M1 Max Chip
Intel Core		Intel Core i5 Processor	Intel Core i7 Processor

In this example we could consider the 'Computers and 'Processor brand' as the two classes. On the other hand, the properties in the case of the Computers class that are considered attributes would be:

• Computers have a screen (Computer -> has a screen -> Screen)
• Computers have a CPU (Computer - > has CPU -> CPU)
• Computers reach a storage (Computer -> Reaches a storage -> Storage)
• Computers have a fingerprint (Computer -> Has a fingerprint -> Fingerprint)

However, with respect to the property 'Computers have processor brand', this is a relation, since it relates our two classes. The property 'Computers have processor brand', is a relation that connects the class computers and the class processor brand. It could be said that the ontology lays the foundations for the Knowledge Graph to capture the data in it and create from the ontology + the individual data set the graphs and represent the information by means of relations, nodes and vertices. That is, a Knowledge Graph is created from an ontology added to a set of individual data.

Decentralized knowledge graphs

As you may have noticed by now, graph-like data structures share certain characteristics with a blockchain and that is why researchers and companies have started to implement algorithms to combine a graph structure and Blockchain technology. A clear example is what is known as a decentralized Knowledge Graph, from the OriginTrail project. As its name suggests it is designed to provide a public and shared infrastructure for information exchange within the knowledge graph. For the full transition to web3, decentralized, verifiable and permissionless knowledge graphs are a very important element for mass adaptation.

Currently knowledge graphs are used on the web2 in a centralized way by companies such as Amazon, Google, IBM, etc... to search, integrate, analyze and apply machine learning through AI to all the data they process. The idea of the OriginTrail project is to have a decentralized knowledge graph without a central authority managing the data, being thus the data managed in a blockchain and connected to a knowledge graph which can be accessed for both 'Publish' and 'Query' operations without permission and DApps can do searches, integrations, analytics, AI and ML for any data source. The first data layer where basic information is given, has been standardized through DIDs and semantic standards such as W3C and GS1. On the other hand, as indicated on their website, with OriginTrail decentralized Network (ODN) you can be able to query data in a multitude of systems and exchange them through different protocols and store them in local knowledge graphs. A relevant fact is that ODN is compatible with blockchains such as Ethereum, Gnosis, Polygon and Polkadot.

We will not go into detail on how Origintrail's Knowledge Graph Decentralized works, but here is an explanatory video to better understand it.

Watch Video