NetAttac

Complex Systems Summer School 2013 Home Research Assistant Position Details Surveys/Evaluations Logistics Faculty Participants Schedule Lecture Slides Background Readings Software Projects & Working Groups CIB Markov Comedy and Tragedy in Shakespeare Global Emergent Risk NetAttac Cities Matrix Matters Synchrony on Networks Unfolding History Tutorials Blog Glue Session Forum Project Presentations Final Papers After Hours Hiking Photos TShirts Question Of the Week Page

We're thinking about co-evolving a network and an attacker agent to see which topologies emerge in the network and which strategies may be used by agents within the network to create that topology. The starting point of our idea was the question if networks containing nodes that are "too big too fail" may reduce the resilience if directed attacks against important nodes are performed against the network - or if the networks can in fact reorganize rapidly in case of the failure of a central node.

Document with details

Open Issues to be discussed

• Define a proper set of research questions: we should probably come up with some guiding research questions.
• Who is evolving? Agents or the Network? We have to decide if our basic building blocks that evolve are the nodes that apply different linking strategies (i.e. every agent has a genome representing linking strategies) or if the network itself evolves (i.e. the network configuration is the genome). The same applies to the attacker: is there one central attacker or do we have a group of attackers (which may cooperate)
• Fitness of Network components and attackers: we have to find a good fitness measure, which very much is connected with the definition of our evolving entities. If we decide that single nodes evolve, fitness of a single node in the network could be simply survival - and to survive, links to neighbours are necessary, e.g. to harvest energy from the network.
• Network aim: what is the main aim of the network? What is transported through the network and how is this related to the fitness of the network (or the nodes in the network)?
• Resource constraints: we could introduce a single resource, e.g. energy, that may be used either for consumption, for building links, or for transporting over these links.
• Genome: how does the genome of attackers and network (or network nodes) look like?
• Strategies for network components and attackers: which strategies may be implemented by the different agents?
• Real world examples: are there any real world examples we can relate to?

Some further questions on the table:

• Do we consider addition of new nodes? (it depends on the idea of network we have and if we consider it a closed or open system)
• Related to the question above, do we consider a fair process, I mean attacker destroys n links, the net replicates creating n new links? Or attacker can blow up nodes? How do we react? Creating as many links as the node degree?
• When does our evolution/attack finish? Do we set n moves that net and attacker can perform?
• Should we put game theory concepts into the picture? (It is a 2/multi player game) Is there a game theory expert in the group?

Minutes of meeting 7th June

We have decided the following in today's meeting:

• Reference real-life example is terrorist vs CIA or mafia vs police situations.
• The attacker tries to fragment the network, the attacked tries to recostruct it.
• The network we are dealing with is at least in the first place to keep things simple:

- undirected

- unweighted

- no self links

- no duplicate links

• We start with a network already in place.
• The attacker has the whole info about the network.
• The attacked has local information (I guess we didn't finally agreed on it, isn't it?).
• Attack is on nodes, one node per iteration can be removed.
• Attacker has the goal to minimize hierarchy.
• Fitness metric: global reach (proxy for hierarchy).
• The network react to the attack on the node (that has a degree d) by: attaching a new node with degree 1 and creating (d-1) new links between existing nodes.
• The "game" finishes when the network is no more connected.

TODO: define the genetic algorithm, the strategy of the attacked since it has local information (or not?)

If I skipped something please add.

Sorry, I missed previous meeting. Thank you for the notes. I want to clarify last point for myself: “Game finishes when network is no more connected”. Does it mean that to finish a game I need only one node that is fully isolated? (CIA willn’t agree that they should stop their fight with terrorists on this). I was thinking of more realistic game: CIA goal is to destroy all nodes (especially if they know all network). And node is destroyed if it is attacked directly or if it got isolated. Game finishes when no nodes remain. All the rest of procedure – adding new node and re-linking nodes is the same

Elena

The answer as I think it right now is yes. Then the CIA could start two different "new games" on the two network partitions and try to destroy those as well. We can talk about it in the next meeting. -- Andrea

Another question: how many rounds does the game go? My suggestion is that the number should be random. -- David

Hmmm we can set a minimum + a random number -- Andrea

Possible Tools

Java with jung library Python with networkX

Comment: I (Andrea) looked into networkX (we were mentioning it yesterday) a bit and all the metrics to analyze and the generation of graphs seems to be there.

Viualization with gephi ?

Version control / coordination via GitHub?

Meetings

June 7th, 1h30pm

Next meeting is: Tuesday @ 15.00

Background reading

• [1]

• [2]

• on Networks

• [3] Banković, Zorana, et al. "Improving network security using genetic algorithm approach." Computers & Electrical Engineering 33.5 (2007): 438-451.

• [4] Gross, Thilo, and Bernd Blasius. "Adaptive coevolutionary networks: a review." Journal of the Royal Society Interface 5.20 (2008): 259-271.

• [5] A good paper on how network measures are correlated. This might help us choose which measures to exclude if the computational complexity gets too high.

• A nice experiment testing the classic Red Queen Hypothesis. I'm not sure if you guys are familiar with such hypothesis, which I believe it's a good theoretical background of the project.

• A Novel Network Survivability Analysis and Evaluation Model

• Modeling the coevolution of network and behaviour

• Classic paper on topology and robustness to attacks

Apparently interesting stuff, but we'd have to pay to see (unless there's a hacker int he group..)

• Coevolution of strategy and structure on social networks

• Network Survivability Analysis Based on Stochastic Game Model

Dropbox material

I have created a simple initial file in python/networkX disrupting a random network using betweenness centrality as the metric to find the most important node. If you write down your mail associated to your dropbox account we can start sharing material (David you can share your code for the hierarchy measure), I'll send you an invitation to the share. -- Andrea

Thanks a lot, I'm interested in the code! My e-mail address is johannes dot schmidt at boku dot ac dot at

Real Data

This data set with real terrorist "social network" in case we want to use some real data