# Graph-Based Taxonomic Semantic Class Labeling
## 3 Graph-Based Taxonomic Semantic Associative Community Labeling
### Graph-Theoretical Foundations
#### 3.1.1 Semi-Local Integration Measure  
For the task of analyzing the common semantic features of lexeme nodes in a lexical graph, the most important and representative nodes are those that are strongly integrated into the graph clusters, i.e., those that are closely related to many other nodes in the network structure. Among numerous centrality measures that compute various network properties, the measure that best evaluates the above graph features is the \(SLI\) measure introduced in [7]. The \(SLI\) node importance effectively identifies and evaluates the degree of integration of a node with other nodes in the clusters of a complex network. Hence, the SLI node centrality values for nodes in the subgraphs are integrated into the procedure of semantic class label propagation.  
For better readability, we provide a brief explanation of the \(SLI\) definition for undirected and weighted graphs. Given a graph \(G=(V,E)\) with the set of nodes \(V\) and the set of edges \(E\), let \(E_{a}\) denote the set of all immediate neighbours of \(a\),  
\[E_{a}:=\{x\mid e_{ax}\in E\}.\]  
Both the _weighted degree_ (_strength_) of the nodes, denoted with \(d^{w}(x)\), and the weight of edges, denoted with \(w(e)\), play a part in the \(SLI\) calculation. Another important piece of information participating in the \(SLI\) calculation is the cycle basis of the graph \(G\), denoted by \(P(G)\). The number of simple cycles containing the edge \(e\), denoted by \(p(e)\), contributes to the importance of nodes incident to \(e\). The higher the number of cycles in the local subgraph that include the edge, the higher the integration in the cluster.  
The assignment of the \(SLI\) importance of a node \(a\in V\) starts with the calculation of its importance score \(I(a)\):  
\[I(a):=d^{w}(a)+\sum_{e_{ab}\in E_{a}}I(e_{ab}), \tag{1}\]  
where \(I(e_{ab})\) is the importance score of the edge between nodes \(a\) and \(b\). That is, to emphasize the interconnection of the node \(a\) in the local subgraph, the _weighted degree_ of \(a\) is boosted by the edge importance score of all of its incident edges, i.e., by the strength of its connection to the other nodes in the neighborhood. The edge importance score, \(I(e_{ab})\), is defined as:\[I(e_{ab}):=\lambda(e)\cdot\left(d^{av}(a)+d^{av}(b)-2w(e)\right)\cdot\frac{w(e) \cdot d^{w}(a)}{d^{w}(a)+d^{av}(b)}, \tag{2}\]  
where the edge cycle factor of the edge \(e\in E\) is given by:  
\[\lambda(e):=p(e)+1. \tag{3}\]  
Finally, for easier interpretability, the node importance score \(I(a)\) is normalized, representing the corresponding percentile of the overall node importance in the graph, i.e.,  
\[SLI\left(a\right):=\frac{I(a)}{S_{G}}\cdot 100, \tag{4}\]  
where \(S_{G}\) is the sum of the importance scores of all nodes of \(G\):  
\[S_{G}:=\sum_{b\in V}I(b).\]  
For more details and a computational representation of the SLI formula, see [7]. Additionally, the Python function that implements the \(SLI\) measure is open-source and available in the GitHub repository [49].