Summarizing semantic graphs: a survey <s> Inspired by text summarization and information retrieval <s> In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency. The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods. In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to “catch” the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods. Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time. <s> BIB001 </s> Summarizing semantic graphs: a survey <s> Inspired by text summarization and information retrieval <s> Ontology summarization is very important to quick understanding and selection of ontologies. In this paper, we study extractive summarization of ontology. We propose a notion of RDF sentence as the basic unit of summarization. An RDF Sentence Graph is proposed to characterize the links between RDF sentences derived from a given ontology. The salience of each RDF sentence is assessed in terms of its "centrality" in the graph. We propose to summarize an ontology by extracting a set of salient RDF sentences according to a re-ranking strategy. We compare several measurements in assessing the salience of RDF sentences and give an overall evaluation of experiment results, which shows that our approach to ontology summarization is feasible. <s> BIB002 </s> Summarizing semantic graphs: a survey <s> Inspired by text summarization and information retrieval <s> In this paper we address the issue of identifying the concepts in an ontology, which best summarize what the ontology is about. Our approach combines a number of criteria, drawn from cognitive science, network topology, and lexical statistics. In the paper we show two versions of our algorithm, which have been evaluated against the results produced by human experts. We report that the latest version of the algorithm performs very well, exhibiting an excellent degree of correlation with the choices of the experts. While the generation of automatic methods for ontology summarization is an interesting research issue in itself, the work described here also provides a basis for novel approaches to a variety of ontology engineering tasks, including ontology matching, automatic classification, ontology modularization, and ontology evaluation. <s> BIB003 </s> Summarizing semantic graphs: a survey <s> Inspired by text summarization and information retrieval <s> In the Semantic Web, vocabularies are defined and shared among knowledge workers to describe linked data for scientific, industrial or daily life usage. With the rapid growth of online vocabularies, there is an emergent need for approaches helping users understand vocabularies quickly. In this paper, we study the summarization of vocabularies to help users understand vocabularies. Vocabulary summarization is based on the structural analysis and pragmatics statistics in the global Semantic Web. Local Bipartite Model and Expanded Bipartite Model of a vocabulary are proposed to characterize the structure in a vocabulary and links between vocabularies. A structural importance for each RDF sentence in the vocabulary is assessed using link analysis. Meanwhile, pragmatics importance of each RDF sentence is assessed using the statistics of instantiation of its terms in the Semantic Web. Summaries are produced by extracting important RDF sentences in vocabularies under a re-ranking strategy. Preliminary experiments show that it is feasible to help users understand a vocabulary through its summary. <s> BIB004
One way of summarizing data, especially when the summary is meant for human users, is to select a most significant subset thereof. Such summarization is very useful, considering that the human ability to process information does not change as the available data volumes grow. We describe here RDF knowledge base summarization efforts inspired from information retrieval and text summarization. In  , the authors study the problem of selecting the most important part of an RDF graph which is to be shown to a user interested in a certain entity (resource). A fixed space (triple) budget is to be used; beyond labels, authors also allow the edges of the RDF graph to carry weights, with higherweight edges being more important to show. The authors provide algorithms which select triples favoring closeness to the target entity and weight; then, they extend this with criteria based on diversity (include edges with different labels in the selection) and popularity (favor frequently occurring edge labels). It is worth noting that similar techniques have recently been included in Google's search engine, when the user searches for an entity present in Google's Knowledge Graph, and is presented with a small selection of this entity's properties. Besides this, text summarization principles, where a text can be seen as a collection of terms or a bag of sentences, have been applied to summarize ontologies. An ontology summarization method along these lines is introduced in BIB002 , based on RDF Sentence Graphs. An RDF Sentence Graph is a weighted, directed graph where each vertex represents an RDF sentence, which is a set of RDF Schema statements as illustrated in Fig. 7 . A link between two sentences exists, if an object of one sentence belongs to another sentence as well. The creation of a sentence graph is customized by domain experts, who provide as input the desired summary size, and their navigation preferences, i.e., weights in the links they are mostly interested in. Then, the importance of each RDF sentence is assessed by determining its centrality in the sentence graph. The authors compare different centrality measures (based on node degree, betweenness, and the PageRank and HITS scores, and show that weighted in-degree centrality and some eigenvector-based centralities produce better results. Finally, the most important RDF sentences are re-ranked considering the coherence of the summary and the coverage of the original ontology, and the constructed result is returned to the user. This method does not handle implicit information (thus, it should be applied to a saturated ontology); also, it does not consider the instance graph. Subsequently, the authors extended their technique from one ontology, to the global set of ontologies harvested from the semantic web BIB004 . Specifically, to decide the impor- Instance System tance (salience) of an RDF sentence, they extend it with neighboring information, for example counting how often the terms of the sentence are linked or instantiated in the global semantic web. Two salience measures are proposed: structural and pragmatic importance. Structural importance measures the number of entities in the web that have a reference to the local RDF sentences with regard to subjects, predicates or objects. Secondly, the pragmatics importance takes into account the statistical frequency of terms instantiated across the global semantic web. The two measures are combined in order to produce an integrated importance value for each RDF sentence, which again is passed to a re-ranking step to ensure coverage over the whole ontology. Although, in the second approach, statistical information over the instances is considered, the approach still does not consider implicit information. KCE  BIB003 , on the other hand, attempts to automatically identify the key concepts in an ontology. To achieve this, it combines cognitive principles with lexical and topological measures (the density and the coverage). The goal is to identify a number of concepts that would be selected by human experts. To this direction a number of criteria are defined: -The notion of natural category is used for identifying concepts that are information-rich in a psycho-linguistic sense. This is approximated by two measures: (i) name Fig. 7 Sample RDF sentences BIB002 simplicity promotes concepts labeled with simple names and penalizes compounds; (ii) basic level measures how central a concept is in the taxonomy of the ontology. This is combined with the density favouring concepts which have many properties and taxonomic relationships. -The coverage tires to ensure that no part of the ontology is neglected. -Lastly, the notion of popularity, is based on lexical statistics, and tries to identify concepts commonly used in natural language. Each ontology concept is assigned a score, which is a weighted sum of the scores assigned for each individual criterium; then, the key concepts of the ontologies are taken to be those with the highest score. This approach extracts only schema elements, based on both schema and instance information. Implicit information in the ontology is also taken into account in the process. To fine-tune result quality, the method requires the user to specify values for a set of parameters. The tool implementing this approach is available online and in open source. BIB001 