Multilevel compression of random walks on networks reveals ...

Multilevel compression of random walks on networks reveals ...

Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems

M. Rosvall and C. T. Bergstrom Presented by Thang N. Dinh CISE Department, University of Florida Introduction Community structure gives 2-level map

of the network Real-world networks, the organization rarely is limited to two levels Flows of commuters in UK

Hierarchical Community structure How many hierarchical levels? How many modules at each level? What are members of each

module? Hierarchical Community structure Hierarchical clustering:

Agglomerative algorithms Divisive algorithms Sales-Pardo, 2007: Deriving hierarchical from node similarities. Clauset et al. 2007, 2008: Divide the

dendogram using Maximum Likelihood Lancichinetti et al. 2009: Local optimization of a fitness function Encoding Network Flows Optimal compression of network flows

Network structure (M. Rosvall, C. T. Bergstrom, PNAS 2008) Top three performers (LFR benchmark, Fortunato et al. 2009) Can be extended to reveal hierarchical structure of network

Encoding network flows Encoding Network Flows Compressing an infinite flow (random walk)

Minimize the expected code length Shannons source coding theorem: Two-level map encoding Each module has a code Within module:

Each node has a code Special exit code Two-level map encoding http://www.mapequation.org/mapde

mo/index.html Two-level map encoding Community structure M, with modules Pi The rate in which code for modules used

Probability of entering modules i Entropy of code for modules The entropy of code for nodes in module i Two-level encoding

Hierarchical map encoding Hierarchical map encoding Algorithm Fast stochastic and recursive search

algorithm Join neighboring nodes -> modules -> super-modules (Brondel. 2008) Recursive operate on modules at any levels Local improvement Submodules movement

Single-node movement Experiments Experiments

Experiments Experiments

Recently Viewed Presentations

  • USDOC/ITA/Commercial Service Green Building Technology Case Studies in

    USDOC/ITA/Commercial Service Green Building Technology Case Studies in

    PowerPoint Presentation - Slide 1 Author: Tobias Matkowitz Last modified by ... _PPT_Template 8_JC_PPT_Template 9_JC_PPT_Template 10_JC_PPT_Template 11_JC_PPT_Template 12_JC_PPT_Template 13_JC_PPT_Template Green Building Technology Case Studies in Energy and Environmental Leadership Building ...
  • Joint Basics - Concrete Pipe

    Joint Basics - Concrete Pipe

    1st Concrete Pipe In U.S.?. Mohawk, NY 1842. What type of pipe joint? Rigid Rugged Resilient. It is widely accepted that a 6-inch diameter concrete pipeline, constructed between 1840 and 1842 at the Mohawk New York home of General Francis...
  • Tax Levy Ordinances and Truth and Taxation Requirements

    Tax Levy Ordinances and Truth and Taxation Requirements

    Tax Levy Ordinances and Truth and Taxation Requirements . POWER TO TAX. PROPERTY TAXES - IN GENERAL. ... Property taxes must have a legitimate corporate purpose: Promote the general welfare of the municipality, and ... showing compliance with the Illinois...
  • Title

    Title

    Robert Wagenaar University Groningen, EMJMD Euroculture Member of the Dutch team of Bologna Experts Main messages packed in 5 sections: Progress in implementing agreed reforms Unlocking the full potential of the EHEA: taking implementation forward Innovation in Learning and Teaching...
  • FA Youth Development Proposals More and Better Players

    FA Youth Development Proposals More and Better Players

    Child-Friendly Football. Please find attached a presentation sharing findings from two years research, presentations and discussions across the country. Please send any thoughts or requests for more support in any particular areas through to [email protected] and will try and help...
  • Chapter 6

    Chapter 6

    Fully dressed. Steps. Choose system boundary. Identify primary actors. Identify goals of primary actors. Define use cases that satisfy the goals. Use case names should start with a verb! Tests. Boss test - is the boss happy? Elementary Business Process...
  • Exploring Assessment for Learning

    Exploring Assessment for Learning

    PAT Maths. Self and peer assessments. Phase 4: Analysing the evidence. Before the moderation process, teachers need to analyse the evidence independently and follow a standardised school process to reach OTJs for a range of students in their class. Teachers...
  • Starfish Retention Solutions Client Pitch

    Starfish Retention Solutions Client Pitch

    Complete the fields to specify the date, time and duration of the appointment. You will receive an email confirmation for this appointment. As the calendar owner, you can add appointments at any date and time, regardless of whether they occur...