Degree centrality is simple measurement to calculate the importance of vertices in a graph 14, 15, 9. The degree centrality of a node is a measure of local centrality of that node and it is determined through the sum of the edges that node has. This scenario is applicable for undirected graph (equation 1). For a directed graph, the degree centrality measure is divided into two categories including in-degree centrality and out-degree centrality. In-degree and out-degree centrality are measured by counting the number of incoming and outgoing link from a particular node (equation 2). Nodes with higher degree centrality (In/out-degree centrality) are usually considered as more important nodes. DC(v) = |Numbero f edges(v)| (1) DCin/out(v) = |Numbero f(incoming/outgoing)edges(v)| (2) B. Closeness Centrality Closeness centrality is another measurement to determine the importance of vertices on a global scale within a graph. In this scenario, the closeness of each node to all other nodes in the graph is calculated as a metric to show the importance of each node. A node is a key node if it can quickly interact with all the others, not only with first neighbors. The simplest notion of closeness is based on the length of the average shortest path between a vertex and all vertices in the graph16, 17. The ClosenessCentrality of node v is calculated in equation 3 where d(v, j) is the minimum number of edges to get from node v to nodeu CC(v) = N ? 1 P u?Gd(v, u) (3) C. Betweenness Centrality Betweenness centrality which is primarily focused on the position of a vertex in a graph is defined as the number of shortest path from all nodes in a graph to all other nodes that pass through a particular node. The betweenness centrality which was originally proposed in 17 concentrates on undirected and unweighted graph. This measure is generalized for directed graphs in 18 and weighted directed graphs in 19. The same as degree centrality, a node with a higher betweenness value is considered more important. BC(v) = X s,v,t ?st(v) ?st (4) Where ?st is the total number of shortest paths from node s to node t and ?st(v) is the total number of those paths pass through node v. D. Bridging Centrality Information flow and topological locality of a node is calculated through Bridging Centrality measure. Usually, a node connecting densely connected components in a graph is recognized as a node with higher Bridging Centrality value. Bridging Centrality is based on two key factors including betweenness centrality(BC(v)) and bridging coefficient (Brcoe f f icient(v)) of each node. BrC(v) = Brcoe f f icient(v).BC(v) (5) Brcoe f f icient(v) = DC(v) ?1 P i?N(v). 1 DC(i) (6) Where DC(v) is the degree of node v and N(v) is the set of it’s neighbors. E. Harmonic Centrality The modified version of Closeness approach in a graph 20 is named harmonic centrality in which the average distance is replacing with the harmonic mean of all distances. HC(v) = 1 P u,v d(u, v) (7) F. Radiality Radiality calculates the closeness of a particular node to all nodes in a graph through computing the diameter of a graph21. Ra(v) = 1 P u,v 4G ? (1/d(u, v)) (8) where 4G is the diameter of a G G. Ego Centrality Ego Centrality measurement for a node v aims to generate a subgraph of the main graph G including node v and its neighbors and all of the edges between them. Defining the importance of node v to its neighborhood is the ultimate goal of this technique. EC(v) = i=n Xin i=1 Wi ? e.egoi + i=nXout i=1 Wi ? e.egoi (9) where: Wi = i=n Xin i=1 1 v out i + i=nXout i=1 1 v in i (10) where e.ego=1/v out i , vi the adjacent node of a node v using the incoming edge e and e.ego=1/v in i , vi the adjacent node of a node v using the outgoing edge e H. Relative Cardinality The cardinality of a node in a schema graph is the number of instances in data graph corresponding to that node in the schema graph 22. A node with a higher corresponding instances is expected to be more important compare to a node with a lower instances. The relative cardinality measure can be applied to an edge in a schema graph. In this scenario, the cardinality of an edge between two nodes is calculated as the number of corresponding instances to those nodes in schema graph with that specific edge. I. Eigenvector Centrality Usually, nodes with more edges are recognized to be more important nodes in a graph. However, in real-world scenarios, sometimes the importance of the neighbor nodes is a key point in which more important neighbors provides a stronger signal in comparison with quantity of neighbors 23. In fact, eigenvector centrality, can be considered as a degree centrality measurement while we try to incorporate the importance of the neighbors.The eigenvector centrality of node v in a graph G is calculated as a proportional function of the summation of its neighbors centralities 23. EiC(vi) = 1 ? Xn j=1 Aj,iEiC(vj) (11) Where A is adjacency matrix of a graph G and ? is some fixed constant. J. Frequency Frequency measurement is usually applicable for the cases that we can obtain the main ontology through merging several local ontologies. Ontology merging is the process of combining (merging) two or more local ontology in order to reach to one target ontology 24. In 25, they came with this assumption that ontology (O) is a merged ontology from local ontologies (O1,…, On) and the concept C correspond to one or more concepts contained in (O1,…, On). The frequency of concept C is calculated via equation 12. Fr(C) = |Correspondences(c)| |O1, …, On| (12) Where|Correspondences(c)| is the number of concept correspondences involving c and |O1, …, On| is the number of distinct local ontologies. K. Name Simplicity Name simplicity 26 which is originally inspired from 27 under notion of natural categories emphasizes that people characterize the world primarily in terms of basic objects rather than more abstract concepts and it is a useful basis to recognize good representers of an ontology. Name simplicity measurement of a concept c, as we may expect, penalizes concepts consists of compound words while it favors the concepts with a simple name or label. The name simplicity score of a concept is equal to 1 if the name or the label of that concept would be limited to one word. In the case of compound word the name simplicity score is calculated through equation 13 NameS implicity(c) = 1 ? ?(nc ? 1) (13) Where ? is a constant and nc the number of compounds (words) in the label. L. Density Peroni et al. in 26 considered density measure as a structuring criteria to be able to highlight the overall organization of an ontology. This measures the richness of a concept within an ontology based on the number of subconcepts, properties and corresponding instances.There are two sub-measures including global and local density which are calculated as followings:

Categories: Articles


I'm Garrett!

Would you like to get a custom essay? How about receiving a customized one?

Check it out