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
Understanding the behavior of phenomena such as synchronization in real-world networks
will ideally aid the development of anomaly detection algorithms over these networks.
- 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
- Fefferman, N., L. Gallos, R. Wright.
"EAGER: Collaborative Research: Algorithmic Framework for Anomaly Detection in Interdependent Networks.''
NSF Grant Proposal, 2016.
- Arenas, A., A. Diaz-Guilera, J. Kurths, Y. Moreno, C. Zhou. "Synchronization in complex networks.''
Physics Reports 469 pp. 93-153, Sep. 2008. Elsevier.
- Rodrigues, F., T. Peron, P. Ji, J. Kurths. "The Kuramoto model in complex networks.''
Physics Reports 610 pp. 1-98, Oct. 2015. Elsevier.
- Acebron, J., L. Bonilla, C. Vicente, F. Ritort, R Spigler. "The Kuramoto model: A simple paradigm for synchronization phenomena.''
Reviews of Modern Physics 77, pp. 137-185, Jan. 2005. The American Physical Society.
- da F. Costa, L., F. A. Rodrigues, G. Travieso, P. R. Villas Boas. "Characterization of complex networks: A survey of measurements."
Advances in Physics, 56:1, pp. 167-242, 2007. DOI: 10.1080/00018730601170527
- Shekhtman, L. M., S. Shai, S. Havlin. "Resilience of networks formed of interdependent modular networks."
New Joural of Physics, 17, 2015. DOI:10.1088/1367-2630/17/12/123007