# Introduction oogle's Page Rank is a link analysis algorithm widely used by search engines to rank web page results. Page Rank assigns scores to sites based on popularity; that is, the more popular the page is, the higher is its assigned score. It utilizes hyper relationships modeled as a directed graph, and express them as an adjacency matrix using real numbers. Moreover, this algorithm incorporates a damping factor within the values of 0 to 1, for the generation of a strongly connected directed graph. However, there are problems associated with determining these specific coefficients. This study proposes an algorithm called Hermitian centrality score, which does not require a damping factor to produce results similar to those of Page Rank, and which can be developed systematically for a specific purpose. The method expresses link relationships between the nodes in a directed graph using the imaginary unit and only requires this graph to be weakly connected, although it applies to a nonweakly connected graph. # II. # Related Works Page Rank [1] [2] of Google's search engine has been a widely investigated algorithm [3], whereas Hermitian centrality score utilizes the Hermitian adjacency matrix that is a newly introduced idea in graph theory by Guo [4]. Sugihara [5] was the first to use the Hermitian adjacency matrix to score a node of a directed graph. # III. Pagerank a) Definitions Definition 1: A semi path is a collection of distinct nodes, ?? 1 , ?? 2 , ?, ?? ?? together with ?? ? 1 links, one from each ?? 1 ?? 2 or ?? 2 ?? 1 , ?? 2 ?? 3 or ?? 3 ?? 2 , ?, ?? ???1 ?? ?? or ?? ?? ?? ???1 . Definition 2: A path is a collection of distinct nodes, ?? 1 , ?? 2 , ? , ?? ?? , together with the links, ?? 1 ?? 2 , ?? 2 ?? 3 ,?, ?? ???1 ?? ?? . Definition 3: A directed graph ?? = (??, ??) is called weakly connected if, for all nodes ?? 1 , ?? 2 ? ?? there exists a semi path between ?? 1 and ?? 2 . Definition 4: A directed graph ?? = (??, ??) is called strongly connected if for all nodes ?? 1 , ?? 2 ? ?? there exists a path from ?? 1 to ?? 2 . # b) Page Rank algorithm Page Rank has three characteristics [2], [6] that can be digested as follows. First, a page receives a high score when it has an inline from a node with a high score. Second, a page catches a high score when it has many in lines. Third, a page receives a high score when it has an inline from a node with few outlines. Thus, the selected outline to the page is important to obtain a high score. Page Rank considers the score of a node in a directed graph based on the nodes that have an outline to the node without taking into account a node that has an inline from the node. The Page Rank scores of the nodes of a directed graph are defined as follows [7]. Let |?? ?? |be the number of outlines from a node ??. We define the ?? × ?? matrix ?? ???? as follows: ?? ???? = 1/|?? ?? | if there is a link from node ?? to node ?? and equals 0 otherwise. We define the matrix ?? as follows using ?? ?? to designate a row vector of all 1s. ?? = ?? + ??((1/??)?? ?? ), where ?? ?? = 1 if node ?? has no outline and 0 otherwise. We define the matrix ?? as follows: ?? = ???? + (1 ? ??)(1/??)???? ?? . The PageRank scores are the elements of the normalized dominant lefthand eigenvector of ?? that corresponds to the real dominant eigenvalue, 1. The dominant eigenvalue is defined as the absolute maximum eigenvalue of a square matrix. The coefficient ?? in the equation is called ?? = ??(??) > 0, ?? ? ??(??), and the multiplicity of the eigenvalue is 1. Here, ??(??) is the spectral radius of ??, and ??(??) is the spectrum of ?? [8]. Therefore, a real positive dominant eigenvalue exists. Also, this value is unique because the multiplicity is 1. Otherwise, a dominant eigenvalue cannot be determined. In this model, the damping factor, ??, can be understood as a parameter that controls the proportion of time that a user follows the hyperlinks, as opposed to randomly jumping to new webpages. If, for example, ?? = 0.85, then 85% of the time, the user uses the hyperlink structure of the Internet, and the other 15% of the time, s/he goes to a random new page [7]. # c) Problems PageRank currently faces the following problems. # i. Empirical Labor The selection of a damping factor value is eminently empirical, and in most cases, the value of 0.85 proposed by Brian and Page is used [9]. With the damping factor value 0.85, the directed graph in Figure 1 has the ranking 3, 5 = 7, 4 = 6 = 9, 2, 1 = 8. # ii. Inconsistent Rankings A network has inconsistent rankings when using different damping factor values [10]. An example of this case is shown in Figure 2. As stated in the abovementioned empirical labor problem, we do not know how the ranking of the nodes will be changed before we increase the damping factor from 0 to 1. # iii. Possible Use for Spam A specific damping factor value could be used to create spam against a search engine [11]. # iv. Fixed Top-Ranking Node This problem means that the top-ranking node of a directed graph is fixed for all damping factor values from 0 to 1 even though we would like another node to be recognized as the top ranking. For example, in the directed graph in Figure 1, node 3 is the top-ranking node for all damping factor values from 0 to 1, as shown in Figure 2. However, we may choose that nodes 5 and 7 should be the top nodes because there is a path from node 3 to those nodes, and there is no path from nodes 5 and 7 to node 3. # IV. # Hermitian Centrality Score Hermitian centrality score is based on eigenvector centrality [12] in social network analysis [13]. Definition 6: For a directed graph ?? = (??, ??), the Hermitian adjacency matrix ?? is defined in the following # b) Advantage of the Hermitian adjacency matrix An advantage of using the Hermitian adjacency matrix is that eigenvalues of it are always real numbers, because it is a Hermitian matrix. Moreover, the results of trials suggest that, if a directed graph is weakly connected, the absolute dominant eigenvalue, |??| 1 , of the graph's Hermitian adjacency matrix, ??, is a positive number with a multiplicity of 1, a negative number with a multiplicity of 1, or a positive number with a multiplicity of 1 and a negative number with a multiplicity of 1. According to the results of the trials, these conditions are satisfied when we derive the Hermitian matrix ?? ? from ?? using the method described below and when we create the Hermitian matrix ?? ?? from ?? ? with the procedure introduced subsequently in this paper. We select the positive eigenvalue, if the dominant eigenvalues include a positive and a negative real value. # c) Algorithm for the type I Hermitian centrality score The algorithm for the type I Hermitian centrality score of a node of a directed graph is as follows. We use ?? to designate the number of all the nodes of the entire graph. The algorithm is designed to be used for each weakly connected directed graph in the entire graph. Once we derive a score of the node of a weakly connected graph from the algorithm, we can compare it to the score of another node, which belongs to a different weakly connected graph, which is also derived by the algorithm. Stage 1: Label the node with zero inlines at the origin of the longest path as node ??. Stage 2: If there are more than one nodes that satisfy the condition described above, add a dummy node and links from the dummy node to the nodes that satisfy the condition; the dummy node is designated as ??. Second, based on the Type I algorithm, we create the algorithm of Type II Hermitian Centrality Score. Type II algorithm is intended as an alternative to Page Rank. # a) Definitions Definition 5: A node ?? ?? is reachable to a node ?? ?? if there is a path from the former A square matrix ?? is irreducible if and only if its directed graph is strongly connected [8]. According to the Perron-Frobenius theorem, if ?? ? 0 is irreducible, equation (1), using ?? as the imaginary unit [4]. This matrix is a Hermitian matrix because for all ?? and ??, ?? ???? and ?? ???? are complex conjugates each other. Of note Stage 7 of the algorithm for defining the score of node ?? of a graph is the product of 2?? ? ??????(?? ?? ), which is the angle in the clockwise direction from the real axis of the complex plane, and, |?? ?? |, which is the length of the 2-dimensional vector corresponding to the node on the complex plane; both terms derived from the eigenequation of ?? ?? . In Stage 6, when node ?? has an inline from node ?? and an outline to node ??, the 2-dimensional vector of node ?? is created as the composition of the 2-dimensional vector of node ?? rotated by 1 ?? in the counterclockwise direction. We need to convert ?? and ??? using ?? and ?? in Stage 4 to confine all converted 2dimensional vectors of all nodes of any weakly connected graphs, which may be the entire graph itself, in the fourth quadrant, so that ??????(?? ?? ) in Stage 7 does not exceed 2??. Using coefficient ??, we can maintain the length of the converted vector the same as that of the vector before the conversion. In Stage 5, we introduce divisions, which correspond to the number of appearances of ??(?? + ??) to estimate selected outlines. Namely, when node ?? has an inline from node ?? and node ?? has, for example, three outlines, the length of the 2-dimensional vector of node ?? becomes smaller by three times in the composition of the 2-dimensional vector that corresponds node ?? so that in the composition of the 2-dimensional vector of node ??, the contribution of the 2-dimensional vector of node ?? is forced to be smaller. Using Stage 6, we set the 2dimensional vector of node ?? on the real axis of the complex plane so that the result of the product as the score of the node equals 0. directed graph is a weakly connected graph. According to Stage 1, node 1 is ?? because it has zero inlines, and it is on the longest path, i. e., that is 1, 2, 3, 4, 5 (or 1, 2, 3, 6, 7). In the weakly connected graph, each 2dimensional vector ?? ?? in Stage 7 is obtained by the In Figure 3, we plot each complex number corresponding to each 2-dimensional vector ?? ?? on the complex plane. Table 1 shows the type I Hermitian centrality score values of the nodes in Figure 1 and their ranking. # e) Algorithm for the type II Hermitian centrality score We modify the algorithm of the type I Hermitian centrality score to create the type II Hermitian centrality score. The latter can mathematically and systematically change the point of a node of a directed graph, and, it can reproduce the result of Page Rank well. As in the type I, we use ?? to designate the number of all the nodes of the entire graph. As in the type I algorithm, the algorithm is designed to be used for each weakly connected directed graph in the entire graph. Once we derive the score of a node of a weakly connected graph, we can compare it to the score of another node, which belongs to a different weakly connected graph, which is also derived by the algorithm. In those abovementioned considerations, the type I Hermitian centrality score determines the score of a node by considering both of all the node that have an outline to the node and all the nodes that have an inline from the node. # d) Experimental Evaluation of the Type I Hermitian Centrality Score We apply the abovementioned algorithm to the directed graph in Figure 1. In this figure, the entire # ? ? with zero inlines in the weakly connected graph. Of note ?? 1 is the parameter for the distance from the node with zero inlines. This distance is defined in terms of the angle from the real axis on the complex plane. As we increase the value of ?? 1 from 0, the score of the node increases depending on how far away the node is from the node with zero inlines. Of note ?? 2 is the parameter for the selected inlines to the node. As we increase the value of ?? 2 from 0, the score of the node increases depending on how small the number of outlines of the nodes on the path from the node with zero inlines to the node, excluding the node itself. Similar to Page Rank, the algorithm of the type II Hermitian centrality score determines the score of a node by considering all nodes that have an oulink to the node without considering the nodes that have an inline from the node. This point has been made possible by deploying 1 ?? in Stage7 ? . The deployment of 1 ?? is equivalent to eliminate the contribution from the nodes that have an outline to the node in the creation of the 2dimensional vector of the node on the complex plane. # f) Experimental Evaluation of Type II Hermitian Centrality Score i. Directed Graph in Figure 1: fixed ?? 1 and ?? 2 We calculate the type II Hermitian centrality scores of the nodes in the directed graph in Figure 1, by setting ?? 1 = 1 and ?? 2 = 0. In ? on the first subgraph in Figure 1 to obtain and In Figure 6, we plot each complex number, which corresponds to each 2-dimensional vector ?? ?? on the complex plane. Table 2 shows the tentative type II Hermitian centrality score values of the nodes in Figure 4. ii. Directed Graph in Figure 1: changing ?? 1 and ?? 2 For the directed graph in Figure 1, we converted ?? 1 and ?? 2 from 0 to 0.5 with the interval of 0.05. The type II Hermitian centrality score values of nodes 3 and 5 (the score of node 7) are shown in Figure7. Figure7 shows that when ?? 2 = 0, the point of node 5 is always higher than that of node 3; and if ?? 1 = 0, the score of node 3 is higher than that of node 5. The abovementioned results are obtained because ?? 1 is the parameter for the distance from the node with 0 zero inlines, and, ?? 2 is the parameter for selected inlines to the node. Here, the fixed top-ranking node problem of Page Rank with the directed graph in Figure 1 has been solved by the type II Hermitian centrality score. The rankings by the type II Hermitian centrality score of the nodes from Figure 1 become the same as those of Page Rank when ?? 1 = 0.9 and?? 1 = 0.4, as shown in Table 5. # iii. A larger network case The directed graph in Figure 8 is composed of 60 nodes. The links between the nodes in the graph were created randomly and can be reproduced with the "set.seed(000)" for "rgraph(60, tprob=0.014)" command in the sna package for Linux R version 3.4.3. We apply the type II Hermitian centrality algorithm to the graph using the following parameters of ?? 1 and ?? 2 : 0 to 1 with the interval of 0.1. Then, we calculate spearman correlation coefficients between the scores by PageRank using the damping factor of 0.85 and the type II Hermitian centrality score values. The maximal value of the correlation coefficient is 0.9453585 at ?? 1 = 0 and ?? 2 = 0. Namely, the type II Hermitian centrality score can reproduce the result of PageRank well. The scatter plot of the parameters for the PageRank scores and type II scores is shown in Figure 9. multiplication of the number of outlines of each node, which precede the node, excluding the node itself. Second, for node ?? in the weakly connected graph, the final type II Hermitian centrality score is the sum of its scores from its every tentative score in every subgraph induced by all nodes that are reachable from each node 4 shows the final type II Hermitian centrality score values of the nodes of the weakly connected graph in Figure 1. the following equation (3). X = 1 | ? | 1 H '' X x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1 | ? | 1 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 s(t + i) 3 0 s(t + i) 3 0 s(t ? i) 3 s(t + i) 3 0 0 s(t ? i) 3 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 0 0 0 0 0 0 s(t ? i) 3 0 0 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 0 0 0 0 s(t + i) 3 0 0 0 0 0 0 0 0 s(t ? i) 3 0 0 0 0 0 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1.0000000 + 0.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?6! {2? ? arg(x i )} × | x i | ! 2? ? arg(x i ) ! | x i | X = 1 | ? | 1 H '' X x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1 | ? | 1 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 s(t + i) 3 0 s(t + i) 3 0 0 s(t + i) 3 0 0 s(t ? i) 3 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 0 0 0 0 0 0 s(t ? i) 3 0 0 0 s(t + i) 0 0 0 0 0 0 0 s(t ? i) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s(t ? i) 3 0 0 0 0 0 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Global? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?! 1 × 1! 1! 3 × × ! 2? ? arg(x i ) 1! 1! 3! 1 × × × 1! 1! 3 × × 1! 1! 3! 1 × × × Score ! : ! 1 and ! 2 are set to 1 and 0, respectively. [ k 2 + {2? ? arg(x i )} ] × (k 1 + 1 M ) k k Table 3: Tentative Type II Scores of the nodes shown in Figure 5 Figure Table 4: Final Type II Scores of the nodes shown in Figure 1 Table 5: Final Type II Scores of the nodes shown in Figure 1 Node Type II Score of the nodes in Figure 1 k1 and k2 are set to 0.9 and 0.4, respectively. # Conclusion This study showed that the four problems of Page Rank algorithm can be resolved with using the Hermitian centrality method, which does not require a damping factor. The novel algorithm effectively reproduces the ranking results of the Page Rank algorithm using 0.85 as the damping factor. Future research may use a sophisticated mathematical and systematic development of the proposed algorithm to achieve betterscores. 3![Create the Hermitian adjacency matrix ?? of the weakly connected graph. Stage 4: In ??, convert each ?? element to ??(?? + ??) and each ??? element to ??(?? ? ??), which derives ?? ? . Here, In the following part of this paper, first, we develop the algorithm of the Type I Hermitian Centrality Score.](image-2.png "Stage 3 :") 6![Solve the eigenequation and on the plane. Stage 7: The type I Hermitian centrality score value of the node ?? is defined as {2?? ? ??????(?? ?? )} × |?? ?? |.](image-3.png "Stage 6 :") 1![in the clockwise direction and the 2dimensional vector of node ?? rotated by ?? 2 ×](image-4.png "1 ??") ![Beyond Google's PageRank: Complex Number-based Calculations for Node Ranking Global Journal of Computer Science and Technology Volume XIX Issue III Version I](image-5.png "") 656![It is identical to Stage 4 in the type I algorithm. Stage 5 ? : It is identical to Stage 5 in the type I algorithm. Stage It is identical to Stage 6 in the type I algorithm. Stage 7 ? : First, the tentative type II Hermitian centrality score of node ?? in the subgraph including ?? 1 is defined as [?? 2 + {2?? ? ??????(?? ?? )}] × (?? 1 + 1 ?? ). Here, ?? is the Beyond Google's PageRank: Complex Number-based Calculations for Node Ranking Global Journal of Computer Science and Technology Volume XIX Issue III Version I ( )Table 3 shows the tentative type II Hermitian centrality score values of the nodes in the subgraph in Figure 5, which are calculated by adopting Stage 4 ? , and the first part of Stage 7 ? . Table](image-6.png "6 ?:E, Stage 5 ? , Stage 6 ?") 1![Figure 1: Directed graph](image-7.png "Figure 1 :") 2![Figure 2: Rankings of the nodes of the graph with a changing damping factor value shown in Figure 1](image-8.png "Figure 2 :") 3![Figure 3: Complex plane plotting of 2-dimensional vectors of the nodes from Figure 1 focused on the fourth quadrant](image-9.png "Figure 3 :") 4![Figure 4: Nodes Reachable from Node 1 in Figure 1](image-10.png "Figure 4 :") ?=T |`| a ?bb ?designate the solution where is the element corresponding to node in Stage 1, and chose the solution so that equals1. Then, each element of ?? = [?? 1 , ? ? ?3 Year 2019The algorithm of the type II Hermitian CentralityScore:Stage 1Stage 2Stage 3© 2019 Global Journals? : ? : ? : 1Year 2019 Year 2019 © 2019 Global Journals Beyond Google's PageRank: Complex Number-based Calculations for Node Ranking © 2019 Global Journals Beyond Google's PageRank: Complex Number-based Calculations for Node Ranking ## Acknowledgment This research was supported by Nanzan University Pache Research Subsidy I-A-2 for the 2019 academic year. This paper includes a world wide patent application: PCT/JP2018/026560. The application has been approved to be a patent in Japan. * The Anatomy of a Large-Scale Hypertextual Web Search Engine SBrin LPage 1998 Stanford InfoLab Publication Server * The Page Rank Citation Ranking: Bringing Order to the Web LPage SBrin 1999 Stanford Info Lab Publication Server * The Anatomy of Web Search Engines and Large-Scale Alterations in Rankin Algorithms MZ Global Journal of Computer Science and Technology: E Network, Web & Security 15 6 2015 Version 1.0 * 2-Dimensional Plot of the Type II and PageRank Scores of the Nodes shown in Figure 8 9 * Simple eigenvalues of graphs and digraphs. Dissertation Submitted in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in the Department of KJGuo 2015 Mathematics of the Faculty of Science of Simon Fraser University * Using Complex Numbers in Website Ranking Calculations: A Non-ad hoc Alternative to Google's PageRank KSugihara Journal of Software 14 2 2019 * Sythesis Lectures on Human Language Technoogies Data-Intensive Text Processing with Map Reduce JLin CDyer 2010 Morgan & Claypool Publishers * Google's Page Rank and beyond THE SCIENCE OF SEARCH ENGINE RANKINGS ALang Ville CMeyer 2006 Princeton University Press * Matrix Analysis and Applied Linear Algebra CDMeyer Society for Industrial and Applied Mathematics 2000 * SWasserman KFaust Social Network Analysis Methods and Applications CAMBRIDGE UNIVERSITY PRESS 2007 * ALangville CDMeyer the Science of Rating and Ranking WHO'S #1? PRINCETON UNIVERSITY PRESS 2012 * A Deeper Investigation of Page Rank as a Function of the Damping Factor PBoldi 2007 Web information Retrieval and Linear Algebra Algorithm * Damping factor in Google page ranking H.-HFu DK JLin H.-TTsai Applied Stochastic Models in Business and Industry 22 5-6 2006 * Total Rank: ranking without damping-Arbitrary ranking PBoldi Proceedings of the 14th International Conference on the World Wide Web, WWW 2005 the 14th International Conference on the World Wide Web, WWW 2005 2005 * Factoring and Weighting Approaches to Status Scores and Clique Identification PBonacich Journal of Mathematical Sociology 2 1972. 12 Year 2019