In this article, the algorithms of visibility for transforming texts into a complex network is proposed. Keywords and concepts from a set of documents which describe some subject domain are extracted. Numeric values are assigned to each word or phrase using GTF metric, which was proposed in this article instead ordinary TF-IDF metric, that is intended to reflect how important a word is to a document in a collection or corpus. As the result, a time series is constructed. A tool in time series analysis - the visibility graph algorithm is used for constructing a graph of the subject domain. In this article, two actual subject domains (“Information extraction” and “Complex network”) are considered for example. The corpora of documents, which are related to actual subject domains, were considered from an open access repository of electronic preprints arXiv (https://arxiv.org). The proposed algorithm is used for the set of documents, which are related to “Information extraction” and “Complex network”. This article shows that applying GTF metric is more expedient compared with TF-IDF metric in the case when the set of documents describe one subject domain. Also, the results of applying the visibility graph algorithm and the compactified horizontal visibility graph algorithm are compared. This article shows, that in some case using the compactified horizontal visibility graph algorithm gives a network of words with more quantity of connections between concepts compared with using the visibility graph algorithm. An open-source visualization and exploration software for all kinds of graphs and networks Gephi and an original package of specially developed Python modules are used for simulation and visualization as an additional tool. The proposed algorithm can be used for visualization some subject domain, and also for information support systems, enabling to reveal key components of a subject domain. Also, the results of this article can be used for building UI of information retrieval systems, enabling to make a process of search a relevant information easier.
The development of the Internet caused a number of problems, which are related, first of all, with a massive quantity of data in the Web-space, including needless data.
Today on the Internet there is a huge and dynamic information base which is
available for research and analysis. It turned out, that many tasks, which arise during
working with the network information space, have much in common with mathematical
sciences. This fact opens wide opportunities to applying a powerful mathematical tool
[
Due to terabytes of textual data, that are distributed in networks and have been accumulating dynamically, development of new methods and algorithms for analyzing these data is necessary. But also the advantages and disadvantages of algorithms that exist for information retrieval must consider.
A modern development of technologies in some case enable to find relevant information. But the problems of further analytical processing of this information, selection of necessary factual data, detection of development trends in selected subject domain, the relation between concepts, events, and forecasting remain unresolved. More of these problems are actual challenges of a semantic processing of huge dynamical sets of textual data. 2
A subject of this study is actual and most commonly found in various articles of
foreign and domestic scientists. For example, in the works [
In particular, in the works [
In this work, a network of connections between terms and concepts, which go into textual data is building. Building networks of words, the nodes of which are elements of the text, enables to reveal key components of the text. At the same time, the task of determining, which of the important structural elements of the text are also informationally important, is actual.
There are several approaches of constructing networks from the texts (so-called
language networks) and different ways of interpreting nodes and connections. It leads,
accordingly, to various kinds of presenting of such networks. Nodes are connected if
corresponding words are either adjacent in the text [
In this article, a tool in time series analysis – the visibility graph algorithm [
For example, the derived graph of visibility for the time series {0.125, 0.063, 0.042, 0.104, 00.125, 0.063, 0.042, 0.104, 0.125, 0.063, 0.042, 0.104} is presented in Ошибка! Источник ссылки не найден.. In the graph, every node corresponds, in the same order, to series data. The visibility rays between the data define the links connecting nodes in the graph.
There is a connection between nodes if they are in “line of sight” with each other, i.e. if they can be connected by a line that does not cross any other histogram bar. More formally, the visibility criteria is described as follows: two arbitrary data values (ta, ya ) and (tb, yb ) will have visibility, and consequently will become two connected nodes of the associated graph, if any other data (tс, yс ) placed between them fulfills:
Also in the article [
In the works [
xk min{xi , x j} for all tk with ti tk t j .
At the third stage, the network, that was obtained at the previous stages, is compactified. As the result, the new network of words – the compactified horizontal visibility graph is obtained.
In this manner, the compactified horizontal visibility graph algorithm enables to construct of network structures based on texts, in which numeric values are assigned in some manner to each word or phrase. 4
In this article, TF-IDF numeric metric (TF – Term Frequency, IDF — Inverse
Document Frequency) is used for forming of the time series. It is an example of a function
that assigns a number to a word in the text. TF-IDF is the most frequently applied
weighting scheme. Also this a numerical statistic is intended to estimate how
important a word is to a document in a collection or corpus [
TF (term frequency) is a ratio of the number of the word occurs in a document to
the total number of words in the document. In this manner, the weight of a term
(word) ti that occurs in a document is simply proportional to the term frequency. The
term was proposed by Karen Spärck Jones [
TF ni , nk k where ni is a number of occurrences of the term (word) i in the document; nk is a total number of words in the document. k
IDF (inverse document frequency) is an inverse function of the number of documents in which a term occurs. It is the logarithmically scaled inverse fraction of the documents that contain the word, obtained by dividing the total number of documents by the number of documents containing the term and then taking the logarithm of that quotient. Using IDF reduces the weight of widely used terms (words).
D IDF log (di ti ) where D is a total number of documents in the corpus; (di ti ) is the number of documents contain a term ti ( ni 0 ).
In other words, the TF-IDF metric is a product of two members: TF and IDF.
TF IDF TF IDF
A word has high TF-IDF score in a document if it appears in relatively few documents, but appears in this one, and when it appears in a document it tends to appear many times.
After the representation of corpora of documents in a vector view (number of words determines the dimension of the vector), the visibility graph algorithm, which was described above, is used.
In this article, before using the method to constructing networks from the texts, we propose to remove stop word. It enables to removing the words, which are informationally unimportant. We use the stop-dictionary based on various stop-dictionaries, which are available via the links: https://code.google.com/archive/p/stopwords/downloads/; http://www.textfixer.com/tutorials/common-english-words.php.
Also, we propose a global TF metric (GTF), which looks like
GTF ni , nk k where ni is the number of occurrences of the term (word) i in documents of the corpus; nk is a total number of words in the documents of the corpus.
Wordsk, which are occurred not often within a single document, have a low TF metric. But if they occur in every document of corpora, they at real are informationally important in a global context for the considered subject domain. That is why in this article we use a GTF metric. 5.1
In this article, the corpora of 292 documents, which are related with an actual domain – “Information extraction”, were considered from an open access repository of electronic preprints – arXiv (https://arxiv.org) for a period of time 2000-2010.
As the result of applying of a proposed method of constructing networks from the texts, the network of keywords, which are important structural elements of the subject domain, was obtained (Fig. 3).
Based on the results which presented in the Table 1 we can notice that quantity of keywords, which are informationally important, is more in case of applying only GTF metric for the set of documents that describe one subject domain. The keywords, such as “information” and “extraction”, which are informationally important for the considered subject domain, are missed in case of using TF-IDF metric (these keywords have a low TF-IDF). After analyzing the results of research (Table 1) we can make the conclusion that applying only GTF metric is more expedient compared with TFIDF metric in the case when the set of documents describe one subject domain. It can be explained by the fact that words, which are key for the considered subject domain and occur in every document of corpora, have a low IDF (as the result a low TF-IDF). But in fact, these words are informationally important and define the structure of the text. For comparison of the results of applying the visibility graph algorithm and the compactified horizontal visibility graph algorithm, the corpora of 2901 documents, which are related with an actual subject domain – “Complex network”, were considered from an open access repository of electronic preprints – arXiv (https://arxiv.org) for a period of time 2000-2010. As a result of applying of visibility graph algorithms two different networks of words for the considered subject domain, was obtained (Fig. 4, Fig. 5).
After deriving the associated graphs from the visibility algorithms, all the terms are
sorted descending and weight values of CHVG and VG corresponding nodes
according to a number of connections with other nodes are calculated. As the weight, for
example, the authority (or hub) calculated by HITS algorithm [
Comparing the results (Table 2), it may notice, that in the case of applying the compactified horizontal visibility graph algorithm (Fig. 5) there are many words, which have more links than in the case of applying the visibility graph algorithm (Fig. 4).
A general quantity of links is 768 in the case of applying the compactified horizontal visibility graph algorithm, unlike in the case of applying the ordinary visibility graph algorithm, when a general quantity of links is 703. It should be noted, that obtained networks are very complex. That is why we plan to continue our research in this sphere. 6
The method of constructing networks from the texts, so-called language networks, was proposed. Keywords and concepts from the set of documents which describe some subject domain were retrieved. Numeric values were assigned to each word or phrase using GTF metric, which was proposed in this article instead ordinary TF metric. After analyzing the results of the research we made the conclusion that applying only GTF metric is more expedient compared with TF-IDF metric in the case when the set of documents describe one subject domain. As the result, a time series were constructed. A tool in time series analysis – the visibility graph algorithm was used for constructing the graph of the subject domain. After analyzing the results of research the important structural elements of the text were found. It should be noted that these elements of the text also are informationally important and define the structure of the text. There was discovered, that in some case using the compactified horizontal visibility graph algorithm gives a network of words with more quantity of connections between concepts compared with using the visibility graph algorithm. Cause of complexity of obtained networks we plan to continue our research in this sphere.
The proposed method can be used for visualization some subject domain, and also for information support systems, enabling to reveal key components of a subject domain. Also the results of this article can be used for building UI of information retrieval systems, enabling to make a process of search a relevant information easier.