Discontinuity, Nonlinearity, and Complexity
Path Integral Distance for the Automated Data Interpretation
Discontinuity, Nonlinearity, and Complexity 3(3) (2014) 255279  DOI:10.5890/DNC.2014.09.004
D. Volchenkov
Mathematische Physik, Universit¨at Bielefeld, Universit¨atsstraße 25 D33615 Bielefeld, Germany
Download Full Text PDF
Abstract
The process of data interpretation is always based on the implicit introduction of equivalence relations on the set of walks over the database. Every equivalence relation on the set of walks specifies a Markov chain describing the transitions of a discrete time random walk. In order to geometrize and interpret the data, we propose the new distance between data units defined as a “Feynman path integral”, in which all possible paths between any two nodes in a graph model of the data are taken into account, although
some paths are more preferable than others. Such a path integral distance approach to the analysis of databases has proven its efficiency and success, especially on multivariate strongly correlated data where other methods fail to detect structural components (urban planning, historical language phylogenies, music, street fashion traits analysis, etc. ). We believe that it would become an invaluable tool for the intelligent complexity reduction and big data interpretation.
Acknowledgments
Financial support by the project MatheMACS (”Mathematics of Multilevel Anticipatory Complex Systems”), grant agreement no. 318723, funded by the EC Seventh Framework Programme FP7ICT20118 is gratefully acknowledged.
References

[1]  SINTEF (2013, May 22). Big Data, for better or worse: 90% of world’s data generated over last two years, ScienceDaily. Retrieved December 17, 2013, from http://www.sciencedaily.com/releases/2013/05/130522085217.htm. 

[2]  Volchenkov, D. (2013), Markov Chain Scaffolding of Real World Data, Discontinuity, Nonlinearity, and Complexity, 2(3), 289–299— DOI: 10.5890/DNC.2013.08.005. 

[3]  Graham, A., (1987), Nonnegative Matrices and Applicable Topics in Linear Algebra, John Wiley & Sons, New York. 

[4]  Crutchfield, J.P. and Packard, N.H. (1983), Symbolic dynamics of noisy chaos, Physica D: Nonlinear Phenomena,7(13), 201–223. 

[5]  Shaw, R. (1984), The dripping faucet as a model chaotic system, CA Aerial Press, Santa Cruz. 

[6]  Li, W. (1991), On the relationship Between Complexity and Entropy for Markov Chains and Regular Languages Complex systems, 5, 381. 

[7]  Feldman, D.P., McTague, C.S., and Crutchfield, J.P. (2008), The organization of intrinsic computation: Complexityentropy diagrams and the diversity of natural information processing, Chaos, 18, 043106. 

[8]  Chung, F. and Yau, S.T. (2000), Discrete Green’s functions, Journal of Combinatorial Theory (A), 91, 191–214. 

[9]  Blanchard, Ph. and Volchenkov, D., (2011), Introduction to Random Walks on Graphs and Databases, Springer Series in Synergetics, 10, Berlin / Heidelberg. 

[10]  Chung, F.R.K. (1997), Lecture notes on spectral graph theory, AMS Publications Providence. 

[11]  Lovász, L.(1993), Random Walks On Graphs: A Survey, Bolyai Society Mathematical Studies 2: Combinatorics, Paul Erdös is Eighty, 1, Keszthely (Hungary). 

[12]  Coppersmith, D., Tetali, P., and Winkler, P. (1993), Collisions among random walks on a graph, SIAM J. on Discrete Math., 6(3), 363. 

[13]  Kern, H. (2000), VIII. Church Labyrinths”. Through the Labyrinth: Designs and Meaning Over 5,000 Years. Prestel. ISBN 9783791321448. 

[14]  Schuster, C. and Carpenter, E. (1996), Patterns that Connect: Social Symbolism in Ancient & Tribal Art, Harry N. Abrams. Pub. 

[15]  Kac, M. (1947), On the Notion of Recurrence in Discrete Stochastic Processes, Bull. Am. Math. Soc., 53, 1002. [Reprinted in M. Kac Probability, Number Theory, and Statistical Physics: Selected Papers, K. Baclawski, M.D. Donsker (eds.), Cambridge, Mass.: MIT Press, Series: Mathematicians of our time Vol. 14, 231 (1979)]. 

[16]  Erdélyi,I. (1967), On the matrix equation Ax =λ Bx, J. Math. Anal. Appl., 17, 119. 

[17]  Meyer, C.D. (1975) The role of the group generalized inverse in the theory of finite Markov chains, SIAM Rev., 17, 443. 

[18]  Drazin, M.P. (1958), Pseudoinverses in associative rings and semigroups, The American Mathematical Monthly, 65, 506. 

[19]  BenIsrael, A. and Greville, Th.N.E. (2003), Generalized Inverses: Theory and Applications, Springer; 2nd edition. 

[20]  Muir, T. (1960), Treatise on the Theory of Determinants (revised and enlarged by W. H. Metzler), Dover, New York. 

[21]  Robert, P. (1968) On the group inverse of a linear transformation, J. Math. Anal. Appl., 22, 658. 

[22]  Campbell, S.L., Meyer, C.D., and Rose, N.J. (1976), Applications of the Drazin Inverse to Linear Systems of Differential Equations with Singular Constant Coefficients, SIAM J. Appl. Math., 31(3), 411. 

[23]  Hartwig, R.E. (1976),More on the SouriauFrame Algorithm and the Drazin Inverse, SIAM J. Appl. Math., 31 (1), 42. 

[24]  Agaev, R.P. and Chebotarev, P.Yu. (2002), On Determining the Eigenprojection and Components of a Matrix, it Automation and Remote Control, 63 (10), 1537. 

[25]  Noguchi, H. (1996),Mozart: Musical game in C K.516f. Available at http://www.asahinet.or.jp/ rb5hngc/e/k516f.htm. 

[26]  Dahlhaus, C. (2007), Harmony, Grove Music Online, ed. L.Macy at www.grovemusic.com. 

[27]  Thomson,W. (1999), Tonality in Music: A General Theory, Everett Books, San Marino. 

[28]  Burns, E.M. (1999), Intervals, Scales, and Tuning. The Psychology of Music, Second edition, Deutsch, Diana, ed., Academic Press, San Diego. 

[29]  Hillier, B. and Hanson, J. (1984), The Social Logic of Space (1993, reprint, paperback edition ed.), Cambridge University Press, Cambridge. 

[30]  Jiang, B. and Claramunt, C. (2004), Topological analysis of urban street networks, Environment and Planning B: Planning and Design, 31, 151. 

[31]  Wirth, L. (1928), The Ghetto (edition 1988), Studies in Ethnicity; Transaction Publishers, New Brunswick (USA), London (UK). 

[32]  Vaughan, L. (2005), The relationship between physical segregation and social marginalization in the urban environment, World Architecture, 185, 88. 

[33]  Vaughan, L., Chatford, D., and Sahbaz, O. (2005), Space and Exclusion: The Relationship between physical segregation. economic marginalization and poverty in the city, Paper presented to Fifth Intern. Space Syntax Symposium, Delft, Holland. 

[34]  Volchenkov,D. and Blanchard, Ph. (2007), RandomWalks Along the Streets and Channels in Compact Cities : Spectral analysis, Dynamical Modularity, Information, and Statistical Mechanics, Phys. Rev. E, 75, 026104. 

[35]  Volchenkov, D. and Blanchard, Ph. (2007), Scaling and Universality in City Space Syntax: between Zipf andMatthew. Physica A, 387(10), 2353. 

[36]  Blanchard, Ph. and Volchenkov, D. (2009),Mathematical Analysis of Urban Spatial Networks, Springer Series Understanding Complex Systems, Berlin / Heidelberg. 

[37]  Hillier, B. (2004), The common language of space: a way of looking at the social, economic and environmental functioning of cities on a common basis, Bartlett School of Graduate Studies, London. 

[38]  Bolton, R.P. (1922), Building For Profit, Reginald Pelham Bolton. 

[39]  Glaeser, E.L. and Gyourko, J. (2003), Why is Manhattan So Expensive? Manhattan Institute for Policy Research, Civic Report, 39. 

[40]  Matsumoto, Y. (2002), An Introduction to Morse Theory, in Iwanami Series in Modern Mathematics, American Mathematical Soc. 