A method of constructing the frame of a directed graph

Hofuku, I. ; Oshima, K.

International Journal of Applied Mathematics and Computer Science, Tome 23 (2013) no. 4, pp. 823-837.

Résumé

In web search engines, such as Google, the ranking of a particular keyword is determined by mathematical tools, e.g., Pagerank or Hits. However, as the size of the network increases, it becomes increasingly difficult to use keyword ranking to quickly find the information required by an individual user. One reason for this phenomenon is the interference of superfluous information with the link structure. The World Wide Web can be expressed as an enormous directed graph. The purpose of the present study is to provide tools for studying the web as a directed graph in order to find clues to the solution of the problem of interference from superfluous information, and to reform the directed graph to clarify the relationships between the nodes.

Détail

Keywords: directed graph, node clustering, Perron-Frobenius theorem, information retrieval
Mots-clés : graf skierowany, węzeł grafu, twierdzenie Perrona-Frobeniusa, wyszukiwanie informacji

Bibliographie

[1] Amy, N. and Carl, D. (2005). A survey of eigenvector methods for web information retrieval, SIAM Review 47(1): 135–161.

[2] Amy, N. and Carl, D. (2008). Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, NJ.

[3] Aracena, J. and Gomez, L. (2013). Limit cycles and update digraphs in Boolean networks, Discrete Applied Mathematics 161(1–2): 217–243.

[4] Balakrishnan, V.K. (1997). Schaum’s Outline of Theory and Problems of Graph Theory, McGraw-Hill, New York, NY.

[5] Berge, C. (2001). The Theory of Graphs, Dover Pubns, New York, NY.

[6] Berman, A. and Plemmons, R. (1979). Nonnegtive Matrices in the Mathematical Science, Academic Press, New York.

[7] Berry, M., Drmac, Z. and Jessup, E. (1999). Matrices, vector space, and information retrieval, SIAM Review 41(2): 335–362.

[8] Hofuku, I. and Oshima, K. (2006). Rankings schemes for various aspects based on Perron–Frobenius theorem, Information 9(1): 37–52.

[9] Hofuku, I. and Oshima, K. (2008). A controlled absolute ranking method applied to an exam of multiplex choice form, International Journal of Pure and Applied Mathematics 47(2): 267–280.

[10] Hofuku, I. and Oshima, K. (2010a). A mathematical structure of processes for generating rankings through the use of nonnegative irreducible matrices, Applied Mathematics and Information Science 4(1): 125–139.

[11] Hofuku, I. and Oshima, K. (2012). A new ranking model using the power method, Applied Mathematics and Information Science 6(1): 75–84.

[12] Hofuku, I., Yokoi, T. and Oshima, K. (2010b). Measures to represent the properties of nodes in a directed graph, Information 13(3): 537–549.

[13] Lancaster, P. and Tismenetsky, M. (1985). The Theory of Matrices, Academic Press, New York, NY.

[14] Ligęza, A. and Kościelny, J.M. (2008). A new approach to multiple fault diagnosis: A combination of diagnostic matrices, graphs, algebraic and rule-based models. The case of two-layer models, International Journal of Applied Mathematics and Computer Science 18(4): 465–476, DOI: 10.2478/v10006-008-0041-8.

[15] Nilson, L. (2007). The Graphic Syllabus and the Outcomes Map: Communicating Your Course, Jossey-Bass, San Francisco, CA.

[16] Ortega, J. (1990). Numerical Analysis, A Second Course, SIAM, Philadelphia, PA.

[17] Prelim, J. and Demongeot, E. (2013). On the number of update digraphs and its relation with the feedback arc sets and tournaments, Discrete Applied Mathematics 161(10–11): 1345–1355.

[18] Yang, F., Shah, S. and Xiao, D. (2012). Signed directed graph based modeling and its validation from process knowledge and process data, International Journal of Applied Mathematics and Computer Science 22(1): 41–53, DOI: 10.2478/v10006-012-0003-z.

[19] Yokoi, T. and Hofuku, I. (2010). The keyword extraction with the ranking method using ANP, Information 13(3(B)): 1065–1073.