IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v390y2011i12p2421-2428.html
   My bibliography  Save this article

A characterization of horizontal visibility graphs and combinatorics on words

Author

Listed:
  • Gutin, Gregory
  • Mansour, Toufik
  • Severini, Simone

Abstract

A Horizontal Visibility Graph (HVG) is defined in association with an ordered set of non-negative reals. HVGs realize a methodology in the analysis of time series, their degree distribution being a good discriminator between randomness and chaos Luque et al. [B. Luque, L. Lacasa, F. Ballesteros, J. Luque, Horizontal visibility graphs: exact results for random time series, Phys. Rev. E 80 (2009), 046103]. We prove that a graph is an HVG if and only if it is outerplanar and has a Hamilton path. Therefore, an HVG is a noncrossing graph, as defined in algebraic combinatorics Flajolet and Noy [P. Flajolet, M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math., 204 (1999) 203–229]. Our characterization of HVGs implies a linear time recognition algorithm. Treating ordered sets as words, we characterize subfamilies of HVGs highlighting various connections with combinatorial statistics and introducing the notion of a visible pair. With this technique, we determine asymptotically the average number of edges of HVGs.

Suggested Citation

  • Gutin, Gregory & Mansour, Toufik & Severini, Simone, 2011. "A characterization of horizontal visibility graphs and combinatorics on words," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(12), pages 2421-2428.
    • Handle: RePEc:eee:phsmap:v:390:y:2011:i:12:p:2421-2428
    DOI: 10.1016/j.physa.2011.02.031
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437111001580
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2011.02.031?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Xie, Wen-Jie & Zhou, Wei-Xing, 2011. "Horizontal visibility graphs transformed from fractional Brownian motions: Topological properties versus the Hurst index," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(20), pages 3592-3601.
    2. Bartolo Luque & Lucas Lacasa & Fernando J Ballesteros & Alberto Robledo, 2011. "Feigenbaum Graphs: A Complex Network Perspective of Chaos," PLOS ONE, Public Library of Science, vol. 6(9), pages 1-8, September.
    3. Bezsudnov, I.V. & Snarskii, A.A., 2014. "From the time series to the complex networks: The parametric natural visibility graph," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 414(C), pages 53-60.
    4. Lihua Liu & Jing Huang & Huimin Wang, 2020. "Visibility Graph Power Geometric Aggregation Operator and Its Application in Water, Energy and Food Efficiency Evaluation," IJERPH, MDPI, vol. 17(11), pages 1-16, May.
    5. Chen, Shiyu & Hu, Yong & Mahadevan, Sankaran & Deng, Yong, 2014. "A visibility graph averaging aggregation operator," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 403(C), pages 1-12.
    6. Bai, Shiwei & Niu, Min, 2022. "The visibility graph of n-bonacci sequence," Chaos, Solitons & Fractals, Elsevier, vol. 163(C).
    7. Tang, Jinjun & Wang, Yinhai & Wang, Hua & Zhang, Shen & Liu, Fang, 2014. "Dynamic analysis of traffic time series at different temporal scales: A complex networks approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 405(C), pages 303-315.
    8. Schmidt, Jonas & Köhne, Daniel, 2023. "A simple scalable linear time algorithm for horizontal visibility graphs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 616(C).
    9. Vamvakaris, Michail D. & Pantelous, Athanasios A. & Zuev, Konstantin M., 2018. "Time series analysis of S&P 500 index: A horizontal visibility graph approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 41-51.
    10. Dong, Yan & Huang, Wenwen & Liu, Zonghua & Guan, Shuguang, 2013. "Network analysis of time series under the constraint of fixed nearest neighbors," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(4), pages 967-973.
    11. O’Pella, Justin, 2019. "Horizontal visibility graphs are uniquely determined by their directed degree sequence," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    12. Wu, Zhenyu & Shang, Pengjian & Xiong, Hui, 2018. "An improvement of the measurement of time series irreversibility with visibility graph approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 502(C), pages 370-378.

    More about this item

    Keywords

    Networks; Time series;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:390:y:2011:i:12:p:2421-2428. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.