publication . Article . Preprint . 2016

Principal Patterns on Graphs: Discovering Coherent Structures in Datasets

Benzi, Kirell; Ricaud, Benjamin; Vandergheynst, Pierre;
Open Access
  • Published: 03 Feb 2016 Journal: IEEE Transactions on Signal and Information Processing over Networks, volume 2, pages 160-173 (eissn: 2373-7778, Copyright policy)
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • Country: Switzerland
Abstract
Graphs are now ubiquitous in almost every field of research. Recently, new research areas devoted to the analysis of graphs and data associated to their vertices have emerged. Focusing on dynamical processes, we propose a fast, robust and scalable framework for retrieving and analyzing recurring patterns of activity on graphs. Our method relies on a novel type of multilayer graph that encodes the spreading or propagation of events between successive time steps. We demonstrate the versatility of our method by applying it on three different real-world examples. Firstly, we study how rumor spreads on a social network. Secondly, we reveal congestion patterns of pede...
Subjects
free text keywords: Information processing, Vehicle dynamics, Scaling, Vertex (geometry), Data mining, computer.software_genre, computer, Computer science, Social network, business.industry, business, Recommender system, Scalability, Graph, Theoretical computer science, Computer Science - Social and Information Networks, Physics - Data Analysis, Statistics and Probability, Physics - Physics and Society
Related Organizations
43 references, page 1 of 3

[1] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and Sabine S u¨sstrunk. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(11):2274-2282, nov 2012.

[2] Alexandre Alahi, Vignesh Ramanathan, and Li Fei-Fei. Socially-Aware Large-Scale Crowd Forecasting. In 2014 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, jun 2014.

[3] Sean Eron Anderson. Bit twiddling hacks. http://graphics. stanford. edu/s˜eander/bithacks. html, 2005.

[4] Renzo Angles and Claudio Gutierrez. Survey of graph database models. ACM Computing Surveys (CSUR), 40(1):1, 2008.

[5] Olatz Arbelaitz, Ibai Gurrutxaga, Javier Muguerza, Jesu´ s M Pe´rez, and I n˜igo Perona. An extensive comparative study of cluster validity indices. Pattern Recognition, 46(1):243-256, 2013. [OpenAIRE]

[6] Albert-Laszlo Barabasi. The origin of bursts and heavy tails in human dynamics. Nature, 435(7039):207-211, 2005. [OpenAIRE]

[7] John M Beggs and Dietmar Plenz. Neuronal avalanches in neocortical circuits. The Journal of neuroscience, 23(35):11167-11177, 2003.

[8] Kirell Benzi. Code repository for the analysis of the Higgs boson dataset. https://github.com/epfl-lts2/higgs, 2015.

[9] Kirell Benzi. Code repository for the causal multilayer graph. https://github.com/epfl-lts2/sptgraph, 2015.

[10] Horst Bischof, Alesˇ Leonardis, and Alexander Selb. Mdl principle for robust vector quantisation. Pattern Analysis & Applications, 2(1):59-72, 1999.

[11] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech., 2008(10):P10008, oct 2008.

[12] Geoffray Bonnin and Dietmar Jannach. Automated Generation of Music Playlists: Survey and Experiments. ACM Computing Surveys (CSUR), 47(2):1-35, nov 2014.

[13] Vittoria Colizza, Alain Barrat, Marc Barthe´lemy, and Alessandro Vespignani. The role of the airline transportation network in the prediction and predictability of global epidemics. Proceedings of the National Academy of Sciences of the United States of America, 103(7):2015-2020, 2006.

[14] Manlio De Domenico, Antonio Lima, Paul Mougel, and Mirco Musolesi. The anatomy of a scientific rumor. Scientific reports, 3, 2013.

[15] Manlio De Domenico, Albert Sole´-Ribalta, Emanuele Cozzo, Mikko Kivela¨, Yamir Moreno, Mason A Porter, Sergio Go´ mez, and Alex Arenas. Mathematical formulation of multilayer networks. Physical Review X, 3(4):041022, 2013.

43 references, page 1 of 3
Abstract
Graphs are now ubiquitous in almost every field of research. Recently, new research areas devoted to the analysis of graphs and data associated to their vertices have emerged. Focusing on dynamical processes, we propose a fast, robust and scalable framework for retrieving and analyzing recurring patterns of activity on graphs. Our method relies on a novel type of multilayer graph that encodes the spreading or propagation of events between successive time steps. We demonstrate the versatility of our method by applying it on three different real-world examples. Firstly, we study how rumor spreads on a social network. Secondly, we reveal congestion patterns of pede...
Subjects
free text keywords: Information processing, Vehicle dynamics, Scaling, Vertex (geometry), Data mining, computer.software_genre, computer, Computer science, Social network, business.industry, business, Recommender system, Scalability, Graph, Theoretical computer science, Computer Science - Social and Information Networks, Physics - Data Analysis, Statistics and Probability, Physics - Physics and Society
Related Organizations
43 references, page 1 of 3

[1] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and Sabine S u¨sstrunk. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(11):2274-2282, nov 2012.

[2] Alexandre Alahi, Vignesh Ramanathan, and Li Fei-Fei. Socially-Aware Large-Scale Crowd Forecasting. In 2014 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, jun 2014.

[3] Sean Eron Anderson. Bit twiddling hacks. http://graphics. stanford. edu/s˜eander/bithacks. html, 2005.

[4] Renzo Angles and Claudio Gutierrez. Survey of graph database models. ACM Computing Surveys (CSUR), 40(1):1, 2008.

[5] Olatz Arbelaitz, Ibai Gurrutxaga, Javier Muguerza, Jesu´ s M Pe´rez, and I n˜igo Perona. An extensive comparative study of cluster validity indices. Pattern Recognition, 46(1):243-256, 2013. [OpenAIRE]

[6] Albert-Laszlo Barabasi. The origin of bursts and heavy tails in human dynamics. Nature, 435(7039):207-211, 2005. [OpenAIRE]

[7] John M Beggs and Dietmar Plenz. Neuronal avalanches in neocortical circuits. The Journal of neuroscience, 23(35):11167-11177, 2003.

[8] Kirell Benzi. Code repository for the analysis of the Higgs boson dataset. https://github.com/epfl-lts2/higgs, 2015.

[9] Kirell Benzi. Code repository for the causal multilayer graph. https://github.com/epfl-lts2/sptgraph, 2015.

[10] Horst Bischof, Alesˇ Leonardis, and Alexander Selb. Mdl principle for robust vector quantisation. Pattern Analysis & Applications, 2(1):59-72, 1999.

[11] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech., 2008(10):P10008, oct 2008.

[12] Geoffray Bonnin and Dietmar Jannach. Automated Generation of Music Playlists: Survey and Experiments. ACM Computing Surveys (CSUR), 47(2):1-35, nov 2014.

[13] Vittoria Colizza, Alain Barrat, Marc Barthe´lemy, and Alessandro Vespignani. The role of the airline transportation network in the prediction and predictability of global epidemics. Proceedings of the National Academy of Sciences of the United States of America, 103(7):2015-2020, 2006.

[14] Manlio De Domenico, Antonio Lima, Paul Mougel, and Mirco Musolesi. The anatomy of a scientific rumor. Scientific reports, 3, 2013.

[15] Manlio De Domenico, Albert Sole´-Ribalta, Emanuele Cozzo, Mikko Kivela¨, Yamir Moreno, Mason A Porter, Sergio Go´ mez, and Alex Arenas. Mathematical formulation of multilayer networks. Physical Review X, 3(4):041022, 2013.

43 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue