Transcript Sample CASOS Talk

Destabilization of Adversarial Organizations
with Strategic Interventions: Computational
Organization Approach
Il-Chul Moon
Nov. 19. 2008
KAIST
Computer Science Department
Semantic Web Research Center
Center for Computational Analysis of Social and Organizational Systems
http://www.casos.cs.cmu.edu/
Interesting Topics
•
•
•
=)
You will enjoy this presentation if….
•
•
•
•
•
You like watching Starcraft games between computer players.
You like watching who-talks-to-whom in parties and class rooms.
You like analyzing who will be campus couples.
You are bored with the same old stories in CS, and you want a little
more adventure.
Or, you want to help people with your CS knowledge, practically
Topics
•
•
•
How to computationally represent and reason about our social relations
to others?
How to computationally organize our groups better?
How to computationally predict our future behavior and relations?
July 17, 2015
2
Computer Science Toward
Interdisciplinary Research
Electrical
Eng.
Biology
Management
/Sociology
Linguistics
Operating
Systems
Communications
Graphics
Algorithm
Artificial
Intelligence
July 17, 2015
My Research:
Social
Network
Analysis
Multi-Agent
Simulations
3
•
Social Networks – Some Pictures (1/3)
Relations among people
•
•
Their interactions, proximities, shared knowledge and belief, etc.
During the military CPX, among officers…
July 17, 2015
4
•
Social Networks – Some Pictures (2/3)
Relations among groups
•
Who talked with whom: the Katrina case
July 17, 2015
5
•
Social Networks – Some Pictures (3/3)
Relations among terrorists
•
Global terrorist network, who works with whom
July 17, 2015
6
Multi-Agent Simulations
•
Simulations with many agents
•
•
•
Agents?
•
•
An entity with agency
Agency – the capacity to make choices
Multi-agents
•
A collective of individual entities who
can act according to their wills
A classic example – Schelling’s
segregation model
•
•
•
1968
I don’t want to have neighbors with
different skin color.
http://ccl.northwestern.edu/netlogo/models/S
egregation
July 17, 2015
7
Okay…. Now, I understand a little..
•
•
•
Social networks
•
Multi-agent simulations
•
•
A simulation on collective, individuals, environment…:
Hypothesis tests, robustness tests, strategy tests…
So, where do you use those tools?
•
•
•
•
•
A network of social entities: Interactions, proximities, shared beliefs among
them…
In many fields!
Military and intelligence
•
Develop a better command structure, destroy enemy spy networks…
Commerce
•
Develop a better supply chain, interfere competitors’ business networks…
Sociology and anthropology
• Develop a better infrastructure and social organizations
• Improve group unity, research on human nature, reveal the path of social evolution…
Then, what was your problem?
July 17, 2015
8
Problem Statement
•
•
Destabilization of adversarial organizations
•
•
•
Counterterrorism, Command and Control (C2) structure research
However, adversarial organizations display complex adaptive
characters
•
•
•
•
A critical component
Complex – various types of nodes and links
Adaptive – adapt themselves to changing situations
Destabilization Analysis: Assess and estimate organizations ahead
of their changes, so that friendly forces can intervene in the
entities and links at the most appropriate time and space
We need a framework
•
•
A partially automated intelligence analysis framework
Bridges cutting-edge technologies/theories and the practices of
counterterrorism and C2 structure research
I will show you just a part of my results…
July 17, 2015
9
Embedding social entities in geospatial maps…
MERGING SOCIAL NETWORKS WITH
GEOSPATIAL ANALYSIS
July 17, 2015
10
Geospatially Embedded Social Network
•
Many social networks are often embedded in a
geospatial dimensions
•
Logistic network, Transnational terrorist network, etc
• Agents are seen at
locations, then how to
incorporate this info.
1/16/2008
11
11
Okay, Show me the picture
•
Two visualization of
a social network
among the terrorists
•
•
Hm…….
I don’t know what
this is!
12
Information Entropy Based Analysis
•
•
•
•
Calculate the information entropy
of spatial and network
information.
Cluster social entities based on
the proximity
Render the area optimizing the
spatial and the information
entropy
Olson, Jamie & Carley, Kathleen. (2008). Summarization
and Information Loss in Network Analysis. Link Analysis,
Counterterrorism, and Security Workshop 2008, SIAM
International Conference on Data Mining, Atlanta, GA, USA
13
By the way, we were also talking about the
simulation
• Now, finally, we have a data-structure to include social
•
networks and geospatial distributions.
How to evolve this social network embedded in the geospace? What do we need? What’s the output?
•
•
•
An input deck
•
Organization (the network) and Parameters
A simulation model
•
•
Agent interactions (so typical, so dull, so cliché…)
Agent relocations (!!!)
An output deck
•
Organizational structure (network) evolution over-time
Input Deck
Model
Output
Deck
14
Output Evolved Network
•
•
Evolved social networks and
geospatial distributions
Il-Chul Moon and Kathleen M. Carley,
Modeling and Simulation of Terrorist
Networks in Social and Geospatial
dimensions, IEEE Intelligent Systems,
Special Issue on Social Computing, Vol.
22, pp 40-49, Sep/Oct. 2007
Simulation Model
- Agent interactions
- Agent relocations
- Parameters
15
Mission Execution Gantt Chart and
Geospatial Segregation
•
•
Mission execution
over-time
The agents are
moving to complete
the mission
•
•
•
•
They should be at
different locations to
complete their assigned
tasks.
Early phase of mission
•
Estimated Gantt Chart of Mission
Execution
Training, surveillance
and resource acquisition
Some agent presence in
Pakistan, Somalia, and
Afghanistan
Estimated Personnel Segregation Level
at Locations
Late phase of mission
•
•
Detonation, movement
to embassy
Heavy agent presence
in Kenya and Tanzania
July 17, 2015
16
Geospatial Organizational Element Distribution
Over-Time
Organizational
Element
Transfer
Network
Geospatial
Distribution of
Organizational
Elements
Time 100
July 17, 2015
Time 200
Time 400
Time 800
17
Simulation Model – Dynet-Spatial
•
Dynet-spatial
•
Evolve the network in the social and
geospatial dimensions
•
•
Observe who are the agents of interest in
future
Estimate where are the locations of interest
in future
• In terms of agent segregation
Agent Behavior
Simulation
Process
Select an interaction partner agent
Time
N
Have remaining
interaction count
for this turn and
not removed
No
Agent 1 Behavior
The partner is actually
removed and the
agent recognize that
the partner is removed
Agent 2 Behavior
No
Agent 3 Behavior
Yes
The agent take-over the
links from the removed agent
to resources, expertise, and tasks.
Remove agents specified in
the intervention strategy sequence
(match the agent ID and timing)
Yes
Select an transferable element (expertise,
resource or element request) and
send or receive the selected element
to or from the partner agent
Exchange transactive memories about
each other agents
Select an geospatial location to relocate
Select one regional resources and expertise to acquire the selected element
Find a ready task to perform
Perform the task and update the status of task if the performance was successful
PilRe loaction 
1
T
K
 AT
t 0 k 0
it
 KTkt  | KLkl |
num.of linkson theshortestpathfroml to k 


| KLkl | 
( # of links VR)

VR  1 ( # of links VR)



18
Transactive Memory in Simulation Model
•
•
•
Information about who knows what
Agents do not know the true status of the organizational structure, but they have
their own transactive memory about the situation.
Agents perform their social behaviors based on their transactive memory.
Transactive memory
transfer over-time
i.e. (Khalfan → Fahid)
Transactive memory
transfer over-time
i.e. (Khalfan → Fahid)
Mohammed’s transactive memory
Khalfan’s transactive memory
July 17, 2015
Source
Target
Abdel’s transactive memory
Source
Target
Khalfan
Purchase
vehicle
Source
Target
Khalfan
Oxygen
Mohammed
Driving
expertise
Khalfan
Fahid
Khalfan
Detonate
Abdel
Mohammed
Abdel
Education
and training
Mohammed
Driving
expertise
Abdel
Education
and training
Abdel
Mohammed
Khalfan
Fahid
Copyright © 2007 Kathleen M. Carley, CASOS, ISRI, SCS, CMU
19
•
•
•
Interaction and Task Execution in
Simulation Model
Dashed lines show potential organizational element requests to other agents.
Solid lines show realized (in simulation) organizational element transfers.
The rectangle shows the mission execution ready status (an agent assigned to a
task has every required organizational element)
July 17, 2015
Copyright © 2007 Kathleen M. Carley, CASOS, ISRI, SCS, CMU
20
Relocation Related Behavior
•
There are four relocation motivation for agents
•
Performing assigned tasks at specific places: An agent may move to a specific
location to perform tasks that have to be done at the location.
•
•
Acquiring required organizational elements: An agent may move to a location where
the agent can acquire expertise and resources required for performing assigned tasks.
•
•
•
If two locations are linked to a task, then the task needs at least two agents to perform the task
because one agent cannot be in two locations.
Regarded a location as an agent by allowing it to provide its resources and information to the
gathering agent. However, a location cannot accept any resources and information.
Facilitating efficient interactions between the interaction partners: An agent may
move to a location where his interaction partner is.
•
By using the boosting factor to simulate the facilitation
Better recovering a removed agent’s links to other agents, resources, expertise
and tasks: An agent is able to better recover a removed agent’s links to organizational
elements by being at the last location where the removed agent was.
July 17, 2015
21
Again, the Outputs….
More informed intelligence and military operation by
anticipating the adversary interactions and
relocations…
22
Simulations with social networks and machine learning…
STRATEGIZING ATTACK COURSES OF
ACTIONS
July 17, 2015
23
So, we know about the enemy, then what?
•
Network destabilization is an important tactic.
•
However, we don’t have complete answers to the following questions.
•
•
•
•
•
Counter terrorism – destabilize a terrorist network to disrupt its plan
Network centric warfare – destabilize a C2 structure to disrupt information
diffusion
Computer network security – destabilize a computer network to disrupt its
function
How to find an efficient network destabilization strategy (or scenario) ?
•
If we remove a node (possibly, agent, resource or knowledge) in a network,
•
•
•
Minimum intervention, maximum destabilization effect
Which node to target?
• Agents with many resources and knowledge vs. Agents at the center of an agentto-agent network
When to remove the node?
• Earlier removal of hub agents and later removal of information-control agents
Vs. Later removal of hub agents and earlier removal of information-control agents
How to assess the located strategy under dynamically changing conditions?
•
•
•
Big damage, but still able to recover
Or, small damage, but unable to recover
Or, big damage and unable to recover
July 17, 2015
24
Course of Action Generation
•
•
•
We limit ourselves to
•
•
•
•
Destabilization of an organization represented in a network structure
Only agent removal strategic intervention
Only one agent removal for a single intervention
Limited number of interventions
We develop a framework
•
•
•
Dynamic network analysis on the target network to reveal its
vulnerabilities
Automatic generation of (optimal) destabilization scenario by using
machine learning technique and network analysis results
Assess the scenarios by utilizing a multi-agent network simulation
model, Dynet, as a test-bed for the developed scenarios
We expect to see
•
•
Better destabilization result from automatically generated scenarios
compared to random destabilization scenarios
An implied trend of the generated destabilization scenarios
July 17, 2015
25
Overall Framework Description
Dynamic Network Analysis
Machine Learning Algorithm
-Calculate network
analysis measures
-Train the algorithm based on
random scenario results
-Generate the scenario based on
the training results
Random Scenario Generator
-Randomly synthesize a removal
scenario
Target Network
Dynet & Near Term Analysis
-Assess the effect of a scenario
with a simulation
•
Located Optimal
Destabilization Scenario
- Assess and compare the
effectiveness to the random
generation case
Integration of three different components
•
•
•
Dynamic Network Analysis
•
reveal the vulnerability and trend
Multi-Agent Simulation Model
•
assess the effect of the scenario
Machine Learning
•
train the non-linear results from the scenario and simulation and compose the optimal
scenario
July 17, 2015
26
A Short Story of Machine Learning Usage
•
•
•
•
•
Time
How to use
machine
learning
algorithms?
Data-points:
Strategy
Training data:
Simulation
result
Train a SVM to
predict the
simulation
outputs
To avoid the
massive
strategy
simulation
Remove
Agent A
Remove
Agent B
Remove
Agent C
Data-points
Agent A’s
Network
centrality,
intervention
timing,
overall
network
status
Simulation
Output
Output to Denote
Agent B’s
Network
centrality,
intervention
timing,
overall
network
status
Agent C’s
Network
centrality,
intervention
timing,
overall
network
status
Estimated
damage to
the enemy
and breakdown
events
Successful
Interventions
Failed
Interventions
July 17, 2015
27
Target Organization:
Dataset – the 1998 US Embassy Bombings in Kenya and
Tanzania
•
•
Agent
ORA Visualization of the
organization
Simple descriptive statistics
of the organization
(numbers in the cells are the
densities of the subnetwork)
Agent
0.143
I use the 1998 US embassy bombings in Kenya and
Tanzania in this presentation.
• Human analysts hand-coded the nodes and
relationships based on a report, Anatomy of a
Terrorist Attack.
Two other datasets, the US embassy bombing in Kenya and
a global counter terrorist organization, are used in the
analysis, as well.
• The results are displayed in the appendix of the thesis.
• To acquire the results, I followed the same procedure
that I will describe by using this dataset.
Expertise
0.126
Location
0.200
(18 terrorists)
Expertise
0.071
(14 expertise)
Location
0.500
Resource
0.076
Task
0.142
0.171
0.107
0.312
(5 locations)
Resource
0.120
(13 resources)
Task
0.055
(25 tasks)
July 17, 2015
28
Best Over-time Destabilization Result
Baseline, a case without
intervention, shows
highest knowledge
diffusion rate.
•
•
•
Random
Selection
Non-isolation
0.9
Same to the previous
slide
Random isolation
sequence shows pretty
damaged diffusion rate,
but the organization is still
able to recover.
•
Knowledge Diffusion of Best Destabilization Strategies of Random Generation and Selection Generation
1
Also, notice the big
variance between the
best case and the
average case
Learning algorithm shows
total break-down of the
organization in terms of
knowledge diffusion.
0.7
Difference
between nointervention and
random
interventions
0.6
0.5
Difference
between random
interventions
and optimized
interventions
0.4
0.3
0.2
0.1
0
July 17, 2015
Random
interventions:
Still able to
recover
0.8
Knowledge Diffusion
•
0
5
10
Optimized
interventions:
Total break point,
no more network
healing
15
20
25
Timing
30
35
40
45
50
29
Trend about Who to Target and When
Average the
•
It happens after
initial isolation of
high degree
centrality agents
10
15
Timing
row degree centrality-knowledge
0
20
0.6
measure degree
0
5
10
15
Timing
row degree centrality-resource
0.45
0.4
0.35
0
5
10
15
Timing
betweenness centrality
0.4
0.2
0.1
0
5
0.2
0.1
0
5
10
15
Timing
knowledge exclusivity
:
0.5
0.4
0.3
0.2
0.1
0
5
10
Timing
15
20
0.3
0.2
0.1
0
5
0.2
10
15
Timing
eigenvector centrality
20
0.55
0.5
0.45
0.4
0.35
20
0
5
10
Timing
task exclusivity
15
20
10
15
Timing
resource exclusivity
0
5
10
Timing
workload
15
20
0
5
10
Timing
15
20
0.15
0.1
0.05
0
20
0.2
0.15
0.1
0.05
0
5
0.2
0.4
0
20
0
1024
Optimized (or
random)
destabilization
scenarios
10
15
Timing
high betweenness and low degree
0.5
0.3
0.5
0.6
0.3
0
20
1
0
20
0.4
0.5
0
0.1
0.05
measure degree
measure degree
measure degree
5
0.55
0
July 17, 2015
0
0.2
0.15
measure degree
Isolations of agents
with exclusive
knowledge are not
the first priority.
0.1
clique count
1.5
measure degree
•
Target nodes with
high betweennes
and low degree,
meaning
connecting nodes
0.2
0.15
measure degree
•
0.3
0.25
measure degree
Next waves of
isolations
of
total degree centrality
0.25
measure degree
•
measures
Target nodes
with
high-degree
first
centrality,the
clique
count, selected
betweenness
centrality,agents
etc
measure degree
•
cognitive demand
0.35
measure degree
Beginning waves of
isolations node-level
measure degree
•
0
5
10
Timing
15
20
0.15
0.1
0.05
0
30
Should consider two dimensions: movements and
communications…
TACTICAL SIMULATIONS FOR TROOP
MOVEMENTS AND COMMUNICATIONS
July 17, 2015
31
Tactical Interventions in Two Dimensions
•
Often, simulated real world systems reside in spatial and social
dimensions simultaneously.
•
•
Global Terrorist Network
Globally Distributed Software Development
•
Simulating only one dimension (a simplified 2D grid world)
•
Additionally, real world events impact both dimensions.
•
•
•
•
# of
terrorists
Might be biased or incomplete to
show
the true emergent
behavior
of
Social links
between
target systems.
two geospatial regions
Location sweeps change social interactions
Apprehensions of terrorist leaders change the geospatial distribution of
terrorists
Need a conceptual model
•
•
•
Explore the integration of multiple dimensions
Create a basis for more realistic models
Perform a simple what-if analysis
July 17, 2015
32
•
•
•
•
•
Multi-Agent Model: Construct-Spatial
- Simple Description
A location holds information
pieces (knowledge)
The information can be
collected by
•
•
Communication (social)
Vision (Spatial)
Agent-toKnowledge
bipartite graph.
(AK)
Not just collecting
Information.
Diffuse it!
Collected
knowledge
Agent-to-Agent
comm. link in
comm. range
Social
Dimension
Limited comm.
distance
Limited vision
range
Purpose :
Too far to be
connected
Agent
Agent-toLocation. This
can change by
movement
Agent can
collect a
knowledge in a
location
Spatial
Dimension
Location
Knowledge
July 17, 2015
33
Initial distribution
•
•
•
Degree of knowledge feed is represented as a color of a map
Initially, agents are distributed across a plane and don’t have a
communication network.
Below is a ‘No what-if scenario’ case, simulate till time 60
Agent
Spatial movement plane
40
40
35
35
30
30
25
25
20
20
15
15
10
10
5
5
5
10
15
20
25
30
35
40
5
10
15
20
25
30
35
40
Social Interaction
July 17, 2015
34
Integration Impact of Two Dimensions
- Unequal Information Diffusion
40
35
30
25
20
15
10
1
0.9
Cumulative rate of knowledge that agents learned
No what-if scenario
simulate till time 60
10 replications
Eight vision range
Eight comm. range
equal distribution
With communications
Without communications
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
5
5
•
•
10
15
20
25
30
35
40
0
0
50
100
150
Sorted Agents
200
250
300
Comparison between “social+spatial” and “spatial”
Social interactions induce unequal information distribution
•
•
Some agents become large information holders through communications
These agents can be easy targets in decreasing the knowledge diffusion
July 17, 2015
35
What-If Scenario: Healing Under Threats
Three what-if scenarios
simulate till time 60
10 replications
Vision/Comm. range=8/8
Agent Removal
(Total 20% of
population)
Time 29
(Before attack)
•
•
Time 30
(Right after attack)
Time 59
(After attack)
Social network healing after spatial attacks
Social network heals differently according to the nature of attacks
•
Devastating what-if scenarios should consider various network healings from
various different spatial attacks
July 17, 2015
36
Three what-if scenarios
(Random, Bridge, Hotspot)
Three different agent types
(Vision/Comm=12/4,8/8,4/12)
simulate till time 60
10 replications
Damage on Knowledge Diffusion
What-If Scenario: Response Surface
0.035
0.03
0.025
0.02
0.015
0.01
0.005
0
-0.005
Hotspot
Comm. intensive
Bridge
Neutral
•
•
Region
Random
Vision intensive
Situation
The damages from attacks differ according to agent types and removal
regions
Response surface from various removal regions and agent attributes
•
Different weakest points according to different agent attributes
•
•
Vision intensive agents → Bridge regions (can’t re-establish comm. links)
Comm. intensive agents → Hot-spot regions (can’t move to hot-spots)
July 17, 2015
37
What-If Scenario: Strategy Combinations
0.05
Damage on Knowledge Diffusion
0.045
Vision intensive-Bridge isolation
Vision intensive-Hotspot isolation
Comm. intensive-Bridge isolation
Comm. intensive-Hotspot isolation
0.04
0.035
0.03
0.025
0.02
0.015
0.01
0.005
0
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
Rates of isolated agents out of the population
•
•
Change the number of removed agents
Worst-case scenario changes
•
i.e. with 20% removal, Comm. intensive-Bridge is preferable, but this preference change
according to the threshold
July 17, 2015
38
Big Picture
• This work helps humans in multiple ways.
•
•
•
Now, the human analysts can handle bigger and more complex
organizations with the support from an integrated computational
analysis tool.
At the same time, the human analysts can apply their knowledge
in the process of the analysis.
Finally, the human analysts can get more realistic analysis
results such as the adversaries’ more complete behavior
estimations, organizational supports for task executions, critical
decision making structures hidden in an observed social
network.
July 17, 2015
39
Big Picture for Computer Scientists
•
•
•
Computer science areas
•
•
•
•
Optimization
Artificial Intelligence
Machine Learning
Algorithmic Network Analysis
Computer science in action
•
•
•
•
Course of action (strategy or tactical plans) optimization
Enemy behavior estimation and reasoning
Clustering critical regions and agents, supporting simulation
results
Finding key contacts, resources and locations
How to turn the pure computer science approaches into
the real world applications?
July 17, 2015
40