| Abstract |
Semantic Web (as the /WWW /itself) can be seen as a decentralized system that self organizes and evolves, scaling to unforeseen conditions, features which are typical of complex systems. A big amount of Semantic Web (SW) schemas expressed in either RDFS or OWL has been developed during the last years. In their majority, they are not specified at the same level of detail and hence, only few classes appear as domain/range of many properties, while most appear as domain/range of few or none. Furthermore, they usually form interconnected graphs as a result of a social collaboration process, which involves the reuse and extension of the classes and properties defined in different schemas. In this setting, it would be interesting to investigate to what extent graph features that emerge in social network analysis, such as power-law degree distributions and the small world phenomenon, could be used to grasp the morphology of existing SW schemas. The knowledge of these features is essential in several contexts. For instance, it can be exploited for selecting or devising efficient index structures and search algorithms or it can be exploited for ontology visualization. Furthermore, it can be useful for revealing emerging conceptual modeling habits. Finally, it can be used for guiding synthetic SW data generation in order to benchmark SW repositories and query languages implementations in a credible manner. For instance, for developing ontology-based repositories that will be able to cope with the expected size of the Semantic Web in the coming years, we need to be able to create large datasets and test now the scalability of storage, query or update methods. This Thesis consists of two parts. The former focuses on the investigation of graph features of real SW schemas, while the latter on the generation of synthetic SW schemas that exhibit those features. Concerning the former part, the well-known graph mining techniques cannot be used as such, since SW schemas are graphs enriched with the semantics of RDFS or OWL specifications. In particular, arcs in these graphs are of different nature, namely, a) arcs representing subsumption relationships among classes, and b) arcs representing relations between classes (e.g. has_a) or attributes (e.g. title), collectively called properties. The existence of arcs of the former kind implies additional arcs of the latter one, e.g., a class inherits the properties of its ancestors. Hence, for each SW schema we essentially need to study two graphs that have the same set of nodes (i.e., classes or literal types), namely, the subsumption, and the property graph. Among the results of our experimental analysis, we briefly mention that the total-degree distribution of the property graph as well as the class descendants distribution of the subsumption graph of real SW schemas follow a power-law. Moreover, the property graph of the their majority exhibits the small world phenomenon. Concerning the latter part of this Thesis, i.e., the generation of synthetic SW schemas whose property and subsumption graphs exhibit the features observed in the real SW schemas, the main challenge that was faced was the generation of the subsumption graph given the in- and out-degree sequence of its transitive closure. This implies the generation of transitively closed graphs given their in- and out-degree sequences, problem that has not been studied before in the literature. We present a reduction of this problem to the Linear Programming one.
|
Σχετικά με τους Κανόνες της Δύναμης και το Σημασιολογικό Ιστό
