A method of constructing the frame of a directed graph

Ichiro Hofuku; Kunio Oshima

doi:10.2478/amcs-2013-0062

.blurhash-client-img { display: none !important; }

A method of constructing the frame of a directed graph

International Journal of Applied Mathematics and Computer Science

Volume 23 (2013): Issue 4 (December 2013)

By: Ichiro Hofuku and Kunio Oshima

Open Access

|Dec 2013

Abstract

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 WorldWideWeb 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.

References

Amy, N. and Carl, D. (2005). A survey of eigenvector methods for web information retrieval, SIAM Review 47(1): 135-161.10.1137/S0036144503424786
Search in Google Scholar
Amy, N. and Carl, D. (2008). Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, NJ.
Search in Google Scholar
Aracena, J. and Gomez, L. (2013). Limit cycles and update digraphs in Boolean networks, Discrete Applied Mathematics 161(1-2): 217-243.10.1016/j.dam.2012.06.013
Search in Google Scholar
Balakrishnan, V.K. (1997). Schaum’s Outline of Theory and Problems of Graph Theory, McGraw-Hill, New York, NY.
Search in Google Scholar
Berge, C. (2001). The Theory of Graphs, Dover Pubns, New York, NY.
Search in Google Scholar
Berman, A. and Plemmons, R. (1979). Nonnegtive Matrices in the Mathematical Science, Academic Press, New York.10.1016/B978-0-12-092250-5.50009-6
Search in Google Scholar
Berry, M., Drmac, Z. and Jessup, E. (1999). Matrices, vector space, and information retrieval, SIAM Review 41(2): 335-362.10.1137/S0036144598347035
Search in Google Scholar
Hofuku, I. and Oshima, K. (2006). Rankings schemes for various aspects based on Perron-Frobenius theorem, Information 9(1): 37-52.
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
Hofuku, I. and Oshima, K. (2012). A new ranking model using the power method, Applied Mathematics and Information Science 6(1): 75-84.
Search in Google Scholar
Hofuku, I., Yokoi, T. and Oshima, K. (2010b). Measures to represent the properties of nodes in a directed graph, Information 13(3): 537-549.
Search in Google Scholar
Lancaster, P. and Tismenetsky, M. (1985). The Theory of Matrices, Academic Press, New York, NY.
Search in Google Scholar
Ligęza, A. and Ko´scielny, 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.10.2478/v10006-008-0041-8
Search in Google Scholar
Nilson, L. (2007). The Graphic Syllabus and the Outcomes Map: Communicating Your Course, Jossey-Bass, San Francisco, CA.
Search in Google Scholar
Ortega, J. (1990). Numerical Analysis, A Second Course, SIAM, Philadelphia, PA.10.1137/1.9781611971323
Search in Google Scholar
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.10.1016/j.dam.2012.12.018
Search in Google Scholar
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.10.2478/v10006-012-0003-z
Search in Google Scholar
Yokoi, T. and Hofuku, I. (2010). The keyword extraction with the ranking method using ANP, Information 13(3(B)): 1065-1073.
Search in Google Scholar