DIMACS
DIMACS REU 2017

General Information

me
Student: Kayla Cummings
School: Pomona College
E-mail: ksc72014[at]mymail[dot]pomona[dot]edu
Project: Synchronization in Modular Networks
Advisors: Dr. Lazaros Gallos, Dr. Rebecca Wright
More info: LinkedIn

Project Description

This project combines concepts from complex network science and cyber-security. Modern infrastructure is built as a network of networks. For example, the Internet depends on access to the power grid, which in turn depends on the power-grid communication network and the energy production network. Research in network anomaly detection systems has focused on single network structures (specifically, the Internet as a single network). The multi-layer structure, though, introduces novel phenomena and calls for new approaches. This summer, I study the effects of modular network topology on synchronization in two-layer networks. Understanding the behavior of phenomena such as synchronization in real-world networks will ideally aid the development of anomaly detection algorithms over these networks.

Weekly Log

Week 1:
I will study some aspect of the Kuramoto Model (KM) of synchronization in complex networks. I met with Dr. Gallos twice this week to define my problem and prepare slides in Beamer for a five-minute presentation next week. To gain an understanding of the KM, I skimmed three literature reviews. I also started to run simulations in R to gain better intuition about the relationships amongst the parameters of the basic KM. Finally, I configured this webpage!
Week 2:
This week started off with a bang when I made my presentation on Monday. Afterward I was able to focus on implementing two versions of the KM in R. The basic KM considers oscillators rotating on the unit circle. Their frequencies fluctuate depending on other oscillators' positions and frequencies as well as their own natural frequencies. For my first implementation, I made the simplest assumption that each oscillator exerts influence over all other oscillators, resulting in a complete neighbor network. I whipped up a function that helps me visualize how global order changes over time for different oscillator coupling strengths. In my second model, I assumed that the neighbor network of oscillators forms a square lattice with periodic boundary conditions and created a function that helps visualize which parts of the lattice have synchronized. I seriously upgraded my graphing skills in R this week, too (shoutout to ggplot2). In other news, I have continued to read several papers to better understand the KM and complex network science. Reading topics have included:
  • Erdos-Renyi, small-world, and scale-free networks,
  • the effect of topological features like clustering, community structure, degree-degree correlation, and average shortest path length on synchronization in complex networks,
  • and a survey of a model of diffusion based on random walks on complex (multilayer) networks.
Week 3:
I implemented a version of the KM that can simulate synchronization on any single-layer network. I also found an R library called igraph that can generate many types of networks, which will save me a lot of time later, so I learned how to use it. I used the networks I generated and the KM I implemented to gain a sense of how the KM manifests with different network topologies. Later in the week, I coded a function that can generate networks with fairly obvious community structure, also called modular networks. Modular networks contain dense subgraphs whose inter-module connections are more sparse. This network structure is of interest because many real-world networks have this property. Finally, I did some work on implementing the KM in multi-layer networks. I am able to generate two-layer networks with any given level of inter-layer connectivity, then use the networks I generate to simulate the KM. These are all productive strides towards our goal for the summer, which is to characterize the effect of random interlayer connections in a two-layer modular network on global and modular synchronization.
Week 4:
Early this week I spent time observing hysteresis in my simulations. This phenomenon encompasses the idea that the point at which a network transitions from randomness to synchronization (or vice versa) is not always deterministic and can be dependent on the network's current state. To observe this in a two-layer network, I implement the KM, wait until the network has stabilized, take data on the global order of the network, add more interlayer edges, and repeat. After the network has synchronized (or it is very clear that it won't), I repeat the process by removing interlayer edges instead. Then I can make observations about the critical connectivity level for each direction. Because collecting data for this took quite a while for networks of significant size, I used my down time to generate modular networks in a more rigorous way, described in a paper by Shekhtman et al. These are nice networks for what I'll be doing next week. Right now I am running a few dozen trials for ten different types of large networks to collect clean reliable data on how coupling strength affects their synchronization levels. Once I am done with this, I will have the library of base data I need to start pairing networks up, connecting them, and studying how modularity affects synchronization levels in these two-layer networks.
Week 5:
This week I had success characterizing the effect of several key parameters on synchronization in modular networks. I learned how to use a pretty powerful 2D plotting tool called Grace so that I could represent these results more effectively than I could in R. I have begun to run simulations to study the effect of interlayer connectivity on synchronization in two-layer modular networks. I have a lot of questions, but I've decided to focus on one interesting case for now. Under certain conditions, some modular networks are only able to synchronize within modules and cannot synchronize globally. I am trying to determine whether there exist interlayer connectivity levels or coupling strengths in two-layer modular networks that are able to trigger global synchronization in one or both layers.
Week 6:
I am in the process of constructing four heat maps that represent the effect of certain parameters on synchronization in modular networks. The first pair will demonstrate global and modular synchronization levels for varied coupling strengths and modularity strengths. The second pairwill be similar, except I will swap modularity strength with the number of modules in the network. As always, this data takes quite a while to generate, especially since I am averaging values over several trials. I am also setting up code that will allow me to collect data that I can use to construct more phase diagrams demonstrating the effect of interlayer connectivity and interlayer coupling strength on synchronization in two-layer modular networks whose layers have identical parameter values. I have also begun preparing for my final presentation next week.
Week 7:
The heat maps are all set and so are two phase diagrams. I spent the majority of this week summarizing what we'd accomplished so far and polishing my final presentation. Tomorrow I make my presentation and start packing to go to Prague!
Week 8:
This week I traveled to Prague. I am in the midst of a lecture series designed to prepare the five of us for understanding more of the Midsummer Combinatorial Workshop. So far we have had three interesting lectures on graph homomorphisms, probabilistic methodology, and universal structures. The last lecture was held in Cesky Krumlov, where we took a weekend vacation to tour the castle there and to go canoeing on the river. This week we also had a chance to traipse around Prague looking for scenic vantage points. I'm having fun!
Weeks 9 and 10:
We have had five lectures this week on fun things like self-avoid random walks and meanders on square lattices, convex sets, and the Ergodic theorem for Markov chains. I also submitted my final REU report and finalized plans to finish up work with my mentors during the school year. Then we attended the first two days of the 22nd MCW. I'm writing this last update from the airport in Prague, laden with souvenirs and feeling happy and thankful for the community we had this summer.

Presentations

References