"New tools and algorithms for directed network analysis"
EC FET Open project NADINE No288956  of European Union



1. Toulouse (CNRS) D.L.Shepelyansky (network coordinator)
2. Twente (UTWE) N.Litvak (node leader)
3. Budapest (MTA_SZTAKI) A.Benczur (node leader)
4. Milano (UMIL) S.Vigna (node leader)

    Project period May 1, 2012 - April 30, 2015
Video presentation of FET NADINE project at Brussels 2012

On the scale of the past ten years, modern societies have developed enormous communication and social networks. Their classification and information retrieval becomes a formidable task for the society. Various search engines have been developed by private companies which are actively used by Internet users. Due to the recent enormous development of World Wide Web and communication networks, new tools and algorithms should be invented to characterize the properties of these networks on a more detailed and precise level. It is also highly important to have new tools to classify and rank enormous amount of network information in a way adapted to internal network structures and characteristics. The project will develop new algorithms to facilitate classification and information retrieval from large directed networks, including PageRank and CheiRank with two-dimensional ranking proposed by partners, using newly developed Monte Carlo methods. The Google matrix formed by the links of the network will be analyzed by analytical tools of Stochastic Processes, Random Matrix Theory and quantum chaos and by efficient numerical methods for large matrix diagonalization including the Arnoldi method. New tools and algorithms produced by the project will create fundamental basis for developers of new types of search and social media services, which will put Europe on leading positions in this important area dominated at present by other countries. NADINE tools will find applications in modern networks, including mobile communication networks which will play more and more important role in future. New characterization of complex networks will allow stakeholders to manage information extraction for social networks, communication and other networks in an efficient and rapid way. The project will create efficient voting systems in social networks that will pave the way for new types of democracy solutions in societies at a high communication level.

WP1 - CheiRank versus PageRank, centrality measures and network structure
WP2 - Network analysis through Google matrix eigenspectrum and eigenstates
WP3 - Applications to voting systems in social networks
WP4 - Applications of new tools and algorithms to real-world network structures
WP5 - Database development of real-world networks
WP6 - Management
WP7 - Dessemination


Left: nodes on PageRank-CheiRank plane; Center: Wikipedia articles on 2DRank plane; Right: Google matrix of Wikipedia for first 200 PageRank nodes

Left to right: partner 1, partner 3, partner 2, partner 4 (Budapest meeting 10 May 2014 - photo by Anna Tolkacheva)

Final review of EC FET Open gave mark "excellent" to NADINE project: Andras Benczur (P3), Dima Shepelyansky (P1), Sebastiano Vigna (P4), Nelly Litvak (P2), Andrea Feltrin (PO) - left to right, EC BU25, Brussels at 2 June 2015