# SumMER: Structural Summarization for RDF/S KGs
## 4 Constructing Schema Summaries
### Computing Centrality Measures  
Schema summarization aims to highlight the most representative concepts of a schema, preserving important information and reducing the size and complexity of the schema [5]. Despite the significance of the problem, there is still no universally accepted measurement on the importance of nodes in an RDF/S graph. In this section, we describe eight alternative measures that have been proposed for capturing importance in directed graphs. We selected the Degree, the Betweenness, the Bridging Centrality, the Harmonic Centrality, the Radiality, the Ego Centrality and in addition HITS and PageRank as they constitute the state-of-the-art measures for generic graphs [13]. The complexities of all measures are shown in Table 1.  
The simplest importance measure for a graph is the Degree (DE) that is defined as the number of edges incident to a node. Definition 3: (Degree) Let \(G_{S}=(V_{S},\,E_{S})\) be an RDF/S schema graph with vs. nodes and \(E_{S}\) edges. The Degree of a node \(v\in\text{vs.}\) is the number of edges incident to the node. The Betweenness (BE) measure is equal to the number of the shortest paths from all nodes to all others that pass through that node. Calculating the betweenness for all nodes in a graph requires the computation of the shortest paths between all nodes. Definition 4: (Betweenness) Let \(G_{S}=(V_{S},\,E_{S})\) be an RDF/S schema graph. The Betweenness of a node \(v\in\text{vs.}\) is defined as follows:  
\[BE(v)=\sum_{s\
eq v\
eq t}\frac{\sigma_{st}(v)}{\sigma_{st}}\]  
where \(\sigma_{st}\) is the total number of shortest paths from node \(s\) to node \(t\) and \(\sigma_{st}(v)\) is the number of those paths that pass-through \(v\), where \(s\
eq v\
eq t\). The Bridging Centrality (BC) tries to identify the information flow and the topological locality of a node in a network. It is widely used for clustering or in order to identify the most critical points interrupting the information flow for network protection and robustness improvement purposes. A node with high Bridging Centrality is a node connecting densely connected components in a graph. The bridging centrality of a node is the product of the betweenness centrality and the bridging coefficient, which measures the global and local features of a node respectively. \begin{table}
\begin{tabular}{c c} \hline \hline
**Measure** & **Complexity** \\ \hline Degree (DE) & \(O(V_{S}+E_{S})\) \\ Betweenness (BE) & \(O(V_{S}\cdot(V_{S}\cdot E_{S}))\) \\ Bridging Centrality (BC) & \(O(V_{S}\cdot(V_{S}\cdot E_{S}))\) \\ Harmonic Centrality (HC) & \(O(V_{S}\cdot(V_{S}+E_{S}))\) \\ Radiality (RA) & \(O(V_{S}\cdot(V_{S}+E_{S}))\) \\ Ego Centrality (EC) & \(O(V_{S}\cdot e_{S})\) \\ Hits & \(O(E_{S}\cdot\delta)\) \\ PageRank (PR) & \(O(\delta\cdot V_{S})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The complexities of the examined importance measures. **Definition 5**. : _(Bridging Centrality) Let \(G_{S}=(V_{S},\,E_{S})\) be an RDF/S schema graph. The bridging centrality of a node \(v\in\textit{vs.}\) is defined as follows:_  
\[BC(v)=B_{C}(v)\cdot BE(v)\]  
_where \(B_{C}(v)\) is the bridging coefficient of a node which determines how well the node is located between high degree nodes and \(BE(v)\) is the betweenness centrality. The bridging coefficient of a node \(v\) is defined:_  
\[B_{c}(v)=\frac{DE(v)^{-1}}{\sum i\in N(v)\frac{1}{DE(i)}}\]  
_where \(DE(v)\) is the degree of node \(v\), and \(N\) (\(v\)) is the set of its neighbors._  
The Harmonic Centrality (HC) is a modification of the Closeness, replacing the average distance with the harmonic mean of all distances, requiring again the computation of the shortest paths between all nodes. **Definition 6**. : _(Harmonic Centrality) Let \(G_{S}=(V_{S},\,E_{S})\) be an RDF/S schema graph.