From Procedures to Declarations: Rethinking SNA with Semantic Technologies
Towards Semantic-Based Social Network Analysis
The paper proposes a semantic-based methodology for Social Network Analysis (SNA) using the Ontology for Graph Theory (OGT). By transitioning from procedural algorithms to declarative SPARQL queries and OWL reasoning, the authors achieve a verifiable and extensible framework for calculating metrics like Betweenness Centrality and Triadic Census.
TL;DR
This paper shifts Social Network Analysis (SNA) from traditional procedural algorithms to a declarative, semantic approach. By defining the Ontology for Graph Theory (OGT), the authors treat paths as first-class RDF resources, allowing complex metrics like Betweenness Centrality and Triadic Census to be calculated via standard SPARQL queries and reasoning.
Background & Motivation: The Procedural Bottleneck
In traditional SNA, calculating an actor's importance or a network's density involves running specific, often isolated, code-heavy algorithms. This creates two main issues:
- Context Gap: Purely topological data is hard to fuse with the "meaning" of the relationships (e.g., distinguishing between a "friend" and a "colleague" during computation).
- Re-computation Waste: In dynamic networks, a single change often triggers a full re-run of path-finding algorithms.
The authors' insight is to use Semantic Web standards (RDF, OWL, SPARQL) to transform the network into an "Enriched Model" where structural relations are explicitly stored as facts.
Methodology: The OGT Framework
The core of the work is the OGT (Ontology for Graph Theory). Unlike previous attempts (like SemSNA), OGT is a general-purpose graph ontology not limited to social networks.
1. The Ontology Structure
OGT defines four primary classes: Node, Edge, Path, and Graph. The innovation lies in the object properties that define how these interact. For instance, the reaches property is transitive, and stronglyConnected is symmetric—properties the reasoner can exploit automatically.
2. Stage-based Query Execution Plan
To build the final model, the authors propose a three-stage refinement process:
- Stage 1 (Initialization): Basic node/edge metrics and the first hop of paths.
- Stage 2 (Iterative Expansion): A recursive SPARQL step that "stretches" paths until all possible paths are materialized.
- Stage 3 (Advanced Analytics): Identification of shortest paths and calculation of centralities.
Experiments: Performance vs. Depth
The authors tested the methodology on both real social networks (KPP, GD'01) and synthetic random graphs.
| Graph | Nodes | Edges | Enriched Triples | Total Time (s) |
|---|---|---|---|---|
| KPP | 193 | 273 | 22,805 | 6 |
| GD | 311 | 645 | 412,754 | 633 |
While the triple count grows significantly (e.g., from 2,891 to 412,754 for the GD graph), the payoff is retrieval speed. Once the model is enriched, a researcher can query "all paths traversing this node" in constant time without running a search algorithm.
Critical Insight: The Value of Path Materialization
The most striking takeaway is the decentralization potential. In standard SNA, distributed computation of Betweenness Centrality is a nightmare due to high communication costs between machines. However, if paths are pre-calculated and stored as RDF resources, these calculations become local aggregations, virtually eliminating communication overhead during the analysis phase.
Limitations & Future Outlook
The "elephant in the room" is complexity. For very dense or massive graphs, the number of paths explodes exponentially. The authors acknowledge this and point toward MapReduce paradigms and incremental updates for dynamic networks as the next frontier for OGT.
Conclusion
By moving SNA into the realm of Semantic Technologies, we gain more than just a new way to calculate metrics; we gain a self-describing network. This work paves the way for "Integrated Knowledge Management," where the structure of the data and its semantic meaning are processed in one unified, declarative environment.