Properties of Communication Graph of Academic Web A.A. Pechnikov 1[0000-0002-0683-0019] 1 Institute of Applied Mathematical Research of the Karelian Research Centre of the Russian Academy of Sciences, 11, Pushkinskaya str., 185910, Petrozavodsk, Russia pechnikov@krc.karelia.ru Abstract. Web graph is the most popular model of real web fragments used in Web science. The study of communities in the web graph contributes to a better understanding of the organization of the web fragment and the processes taking place in it. Communities of the web-graph fragments of the real Web are often poorly differentiated and more difficult meaningful interpretation. It is proposed to select in the web graph a communication graph containing only those verti- ces (and arcs between them) that have counter arcs, and already in it to investi- gate the problem of splitting into communities. By analogy with social studies, the ties implemented through the edges in the communication graph are pro- posed to be called “strong” and all others “weak”. Thematic communities with meaningful interpretation are built on strong ties. At the same time, weak ties facilitate communication between sites that do not have common features in the sphere of activity, geography, subordination, etc., and basically keep the web fragments connected even in the absence of strong ties. Experiments carried out for a fragment of the academic Web of Russia show the possibility of meaning- ful interpretation of the results and the prospects of this approach. Keywords: Web graph, Communication graph, Community in graph, Strength of ties. 1 Introduction The study of graphs of the real (and virtual) world is an important task in many fields, such as biology, sociology, social networks, webometrics, and many others, because they allow you to understand the structure of objects and analyze their properties. It has long been known that University and academic fragments of the Web both in Russia and other countries [1–3] have quite specific properties characterizing their structure. In particular, the corresponding web graph has a large strongly connected component (SCC) and a significant number of "hanging" sites (having either only links made from them, or, more rarely, links made only to them). SCC itself is an interesting object of research, allowing to establish, for example, the presence or absence of the property of the "small world" [4], which, however, does little to explain the processes of hyperlinks between sites fragments of the Web. In this sense, much more food for thought is provided by structural elements of the graph, such as site communities, when more links are made "within" communities Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 415 than between communities. But again, attempts to partition the vertices that make up the maximum connectivity component of a web graph into communities lead to diffi- cult to interpret results. The main idea considered in this work is to build a "hard framework" for a fragment of the Web, leaving only those sites that have counter hyperlinks, and already on this "framework" to check the properties of the partition into communities (such a framework will be called a communication graph). And already further by means of known algorithms the question of structure of communi- ties of tops, the communication graph and the "weak" web graph from which the communication graph is removed is investigated. As a real object of research, the scientific and educational fragment of the Web is taken, for which a meaningful inter- pretation of the results is given. 2 Basic Concepts, Methods and Tools The target set of sites is specified by a direct enumeration of their domain names, and as a result of scanning, all the hyperlinks linking them are found. In the case where sites belong to one type of activity, such a set is called thematic. Accordingly, a (the- matic) fragment of the Web is a target set of sites and a set of hyperlinks linking them [3]. A web graph of Web fragment is a directed graph without loops and multiple arcs, whose vertex set is represented by the target site set, and whose arc set is constructed as follows: two vertices are connected by an arc if there is at least one hyperlink link- ing the corresponding sites. A community (cluster, module, group) of a graph can be informally defined as a set of vertices with more arcs between them than with the other vertices of the graph [5]. More strictly, the partition of a graph into communities can be defined through the notion of modularity. Modularity is a property of a graph and some subdivision of it into subgraphs (community modules). The modularity measure shows how qualitative a given partition is in the sense that there are many arcs lying inside subgraphs- communities and few arcs lying outside subgraphs (connecting communities togeth- er). The modularity measure Q can be given by the following formula [5]:  kk   1 Q  Aij  i j    (ci , c j ).  2m ij  2m  Here m is the number of arcs in the graph; Aij is the element of the adjacency matrix of a graph; ki, kj is the degree of the respective nodes; δ(ci, cj) is Kronecker's symbol calculated by the formula: 1 : if ci  c j  (ci , c j )   , 0 : if ci  c j where ci, cj are the class labels of the corresponding vertices. 416 Accordingly, the best partition into communities is considered to be the partition on which the maximum Q is achieved. BeeCrawler [6] and external hyperlink databases [7] were used for data collection and analysis. The open-source graph visualization platform Gephi [8] was used for the study of web graphs, which, among many, implemented programs for calculating the modularity coefficient and searching for communities in the graph using the algo- rithms proposed in [9]. 3 Fragment of the Scientific and Educational Web of Russia The initial target set of sites of a fragment of the scientific and educational Web of Russia dates from the end of 2017, that is, after the Russian Academy of Medical Sciences and the Russian Academy of Agricultural Sciences (RAAS) joined the Rus- sian Academy of Sciences (RAS), but in the process of creating enlarged structures such as federal research centers, as well as enlarging universities. Such a “footprint” allows us to expect on the fact that a fragment of the Web con- tains fairly stable links between sites that have been formed over the past few years. The initial target set contains 867 objects (it is websites of 279 universities and 588 research institutions). Scientific institutions are understood as organizations of the RAS from the level of institutes to regional scientific centers and boards of the RAS. Website of the RAS itself (www.ras.ru) in the target set is not included, because it is a powerful communicator, significantly distorting the common picture. Further, for the sake of brevity, we will call scientific institutions "institutes". Scanning all 867 sites allows you to get about 20,000 hyperlinks made between these sites, including multiple links. Replace multiple links to single arcs and get a web graph containing 867 vertices and 5030 arcs. A test for connectivity and strong connectivity shows the presence of 73 isolated vertices and 236 hanging (36 vertices do not have incoming arcs and 200 (!) - outgoing). In terms of content, we note that 73 isolated vertices in the vast majority relate to the sites of institutes that were previ- ously part of the RAAS. The only SCC contains 534 vertices and 4026 arcs. A web graph equal to the max- imum SCC has a diameter equal to 10 and a modularity coefficient of 0.398 [10], and is divided into 7 communities containing 40 to 139 vertices. The modularity coeffi- cient indicates a low tendency of sites to organize into communities: the values of Q belong to the segment [-1, 1], and clustering is considered "good" somewhere when Q is greater than 0.6. However, one of the communities built has a good meaningful explanation. It in- cludes 40 vertices corresponding to 4 university sites and 36 institute sites, and a total of 97 arcs (which on average is significantly less than in the SCC web graph). Of the 40 websites, 35 belong to the current Department of agricultural sciences RAS, as well as to the Krasnoyarsk scientific center of Siberian Branch of RAS, Kemerovo Institute of technology of food industry, Kuban state technological University, Voro- nezh state university of forestry and St. Petersburg Mining University. Give comments: 417 * Krasnoyarsk scientific center for the period of the study managed to become a Federal research center, which includes 2 agricultural institutes; * Kemerovo Institute of technology of food industry is close to agriculture; * Kuban state technological university has close ties with agricultural institutes of Kuban; * Voronezh state forestry university has a hyperlink on its website to the website of the Central scientific agricultural library (which falls under the term "institutes»); * St. Petersburg mining university has on its website a hyperlink to the website of the All-Russian Institute of plant genetic resources named after N.I. Vavilov, where there is a section of the journal "Agro-industrial complex", issued by the University library. Apart from the last two cases, we can say that this community has a pronounced agro-industrial theme. 4 The Communication Graph of the Web Graph Newman and coauthors, when solving the problem of splitting a graph into communi- ties, avoid graph orientation when dealing with web graphs. Quoting from [10, p. 026113-5]: “…Some networks are directed, i.e., their edges run in one direction only. The world wide web is an example; links in the web point in one direction only from one web page to another. … However, we have found that in many cases it is better to ignore the directed nature of a network in calculating community structure. Often an edge acts simply as an indication of a connection be- tween two nodes, and its direction is unimportant…”. And if direction (orientation) matters? - Let's look at fig. 1, which shows agro-industrial community. Fig. 1. Web graph “agro-industrial community”. 418 There are questions. Can the website vniiz.org (All-Russian research institute of grain and products of its processing) consider a full member of the community when it does not have hyperlinks to other sites? Can the website spmi.ru (St. Petersburg mining university) consider a member of a community when there are no links to it from other members? The term "community" (Gemeinschaft) originated in German sociology at the end of the XIX century and implies the joint activity of its participants with common goals [11], and in this context the answer to the formulated questions should be nega- tive. Therefore, we will further consider an undirected graph, which by construction implies “joint activity”, namely, counter hyperlinks. A communication graph of a web graph is an undirected graph that has the same set of vertices as the web graph, and the set of edges is constructed according to the following rule: an edge (i, j) belongs to the set of edges of a communication graph if and only if in the web graph there exist arcs (i, j) and (j, i). A communication graph constructed in this way can have several connected components and / or isolated ver- tices. In this case, we exclude isolated vertices (since they do not affect connectivity), and then study the connected components individually, starting with the maximum. The communication graph of the web graph of the scientific and educational Web contains 313 vertices and 468 edges (Fig. 2). Fig. 2. Communication graph of scientific and educational Web. Of the 313 vertices, 67 belong to universities and 246 to institutes, i.e. the proportion of universities in the communication graph has decreased by one tenth. The coloring of the vertices is given according to the resulting partition into communities. 419 The modularity coefficient of this partition is 0.695, which is quite high. Built 13 communities contain from 7 to 51 vertices, of which 4 can be accurately identified by one of two features: geography or scientific direction. Some of the built communities can be given a meaningful (thematic) interpretation. Two "geographical" communities are clearly distinguished: No. 2 – "Ural": 1 university (Perm Polytechnical), 23 institutes of the Ural Branch of RAS and the Research center of fiber optics of RAS from Moscow; No. 10 – "Siberia": 4 Siberian universities, 47 Siberian institutes and 1 Institute from Sevastopol. "Humanitarian" community No. 12 contains 10 institutes (archaeology, ethnogra- phy, linguistic research, linguistics, history, world literature, Slavic studies, philoso- phy) and two universities (Altai State University and Gorno-Altaisk State University). "Medical" community No. 9 is a "star" of websites of medical institutes of Siberia and the Far East, linked to the website of the Siberian Department of medical Scienc- es, but not related to each other. Members of any communication graph community are present in the web graph by construction. However, it is not necessary that all members from the same communi- cation graph community belong to the same web graph community. The reverse is not true: the sites participating in the agro-industrial community of the web graph are completely absent from the communication graph. Now remove all pairs of counter arcs corresponding to the edges of the communi- cation graph from the SCC web graph. The resulting "weak" web graph is large enough – 528 vertices and 3090 arcs, but has a low modularity coefficient of 0.356 and is broken up by 8 communities that do not have a convincing meaningful inter- pretation. Find the maximum SCC of the "weak" web graph, remove all vertices not included in the SCC and get the SCC "weak" web graph with 461 vertices and 2744 arcs. Again, the modularity coefficient remains low. 5 Discussion of Results. Strong and Weak Ties More than 45 years ago, Granovetter [12] proposed the concept of the strength of social ties. All connections are divided into two categories, strong and weak, in order to formalize interpersonal relationships based on the duration and frequency of con- tacts. For example, a strong connection is inherent in friends, and a weak one is inher- ent in neighbors. Let's try to use the concept of communication strength as an analogy for sites, although it is initially clear that the analogy is far from complete, since Granovetter believes that the connections are symmetrical. Take a pair of vertices i, j of a directed graph. If there are arcs (i, j) and (j, i) in the graph, then we will talk about a strong connection of vertices i, j. If for vertices i, j there is only one of the arcs (i, j) or (j, i), then we will talk about a weak connection between vertices i and j. Let's look at the dynamics of changes in the proportion of institutes and universi- ties in the considered graphs, for which we will summarize the data in Table 1. 420 Table 1. Proportion of sites of institutes and universities in graphs. Graph Number Number Proportion Proportion Diame- Average of of arcs of insti- of univer- ter path vertices (edges) tutes sities length Initial web graph 867 5030 0,68 0,32 - - SCC web graph 534 4026 0,67 0,33 10 3,6 Communication web 936 313 0,78 0,22 9 3,45 graph (468) "Weak" web graph 528 3090 0,66 0,34 - - SCC "weak" web 461 2744 0,63 0,37 11 4,2 graph The initial scientific and educational web graph like the SCC web graph contain strong and weak arcs, the communication graph lacks weak arcs, and the" weak "web graph and the SCC "weak" web graph lack strong arcs. From Table 1 it can be seen that the institutes/universities ratio is practically the same for all graphs having weak or strong and weak arcs, but changes dramatically for a graph containing only strong arcs. It can be concluded that strong ties are more inherent in institutions than universities. In [12, p. 1362] it is noted that " ... the stronger the ties the more similar individu- als are to each other in different aspects". This is confirmed in the case of the com- munication graph of the scientific and educational Web. We can say that strong con- nections contribute to the emergence of sustainable thematically "similar" communi- ties. Although there are few such communities, only 4 out of 13, they have a clear meaningful interpretation. However, if the communication graph is "built up" to the SCC web graph (and even more so, to the initial web graph), it turns out that none of the four communities of the communication graph not only was not the basis for communities in web graphs, but even their members were in different communities. It seems that the weak links lead to the erosion of communities. Recall that in the SCC web graph we found an " agro-industrial" community, and in the initial web graph we found 73 isolated vertices also related to agricultural insti- tutes. By linking these two results, the following explanation for this exception can be offered. The websites of the former RAAS simply did not have time to establish links with other sites of the target set. Therefore, those RAAS sites that were somehow connected to each other had few links "outside" and organized a community, and the rest remained isolated. What is the role of weak links? According to Granovetter, weak connections can be characterized as a system of irregular contacts that do not cover the friends of an indi- vidual, but connect him with members of other closely related groups in which he does not belong. From this it follows that an individual can establish relationships with people from a large number of mutually disjoint groups, while not being a mem- ber of each of them. 421 In this sense, weak connections play the role of "bridges" in the graph. Recall that a bridge is an edge of a (undirected) graph whose removal increases the number of connectivity components [13]. Granovetter in [12] says that strong ties are almost never bridges, and as a rule, weak bonds are bridges. In our case, indirect confirma- tion of this fact is the diameter and average path length, which are almost the same in the SCC "weak" web graph, SCC web graph and communication graph (Table 1). That is, the removal of strong ties has almost no effect on the diameter of the graphs, which means that the arcs corresponding to them are often not bridges. Hence the conclusion that the weak ties of the fragment of the Web serve to estab- lish contacts of sites from disjoint groups, which is very important in the sense of obtaining new information that does not lie in the circle of interests of this group. The work was supported by The Russian Foundation for Basic Research, project 18-07-00628-a. References 1. Thelwall, M., Wilkinson, D.: Graph structure in three national academic Webs: Power laws with anomalies. Journal of the American Society for Information Science and Tech- nology 54(8), pp. 706–712 (2003). 2. Ortega, J.L., Aguillo, I.F.: Visualization of the Nordic academic web: Link analysis using social network tools. Information Processing and Management 44(4), pp. 1624–1633 (2008). 3. Pechnikov, A.A.: Metody issledovanija reglamentiruemyh tematicheskih fragmentov Web. Trudy Instituta sistemnogo analiza Rossiiskoi akademii nauk. Serija: Prikladnye problem upravlenija makrosistemami 59, pp. 134–145 (2010). 4. Watts, D.J.; Strogatz, S.H.: Collective dynamics of 'small-world' networks. Nature 393, pp. 440–442 (1998). 5. Ermolin, N.A., Mazalov, V.V., Pechnikov, A.A.: Teoretiko-igrovye metody nahojdenija soobschestv v akademicheskom Webe. Trudy SPIIRAN 55, pp. 237–254 (2017). 6. Pechnikov, A.A., Chernobrovkin, D.I. Adaptive Crawler for External Hyperlinks Search and Acquisition. Automation and Remote Control 75(3), pp. 587–593 (2014). 7. Golovin, A.S., Pechnikov, A.A.: Baza dannyh vneshnih giperssylok dlja issledovanija fragmentov Weba. In: Informacionnaja sreda vuza XXI veka: materialy VII Vserossiiskoi nauchno-prakticheskoi konferencii, pp. 55–57. PetrSU, Petrozavodsk (2013). 8. The Open Graph Viz Platform, https://gephi.org, last accessed 2019/12/03. 9. Blondel, V.D., Guillaume, J-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communi- ties in large networks. Journal of Statistical Mechanics: Theory and Experiment, P10008 (2008). 10. Newman, M.E., Girvan, M. Finding and evaluating community structure in networks. Physical Review E. 69(2), P026113 (2004). 11. Levkina, L.I.: Social’no-istoricheskaja rol’ soobschestv. Rusains, Moscow (2016). 12. Granovetter, M.S.: The Strength of Weak Ties. The American Journal of Sociology 78(6), pp. 1360–1380 (1973). 13. Harary, F.: Graph Theory. Addison-Wesley, Boston (1969).