Maximizing the Extent of Spread in a Dynamic Network

From Anita Borg Institute Wiki

Maximizing the Extent of Spread in Dynamic Network

Presenters:

Habiba Habiba & Tanya Y. Berger-Wolf, University of Illinois at Chicago

Idea of representing network as a graph is not new and has been used over period of time. Relationship between individuals can be represented as links. Spreading of network can be studied as a graph algorithm.
Two types of networks are being compared here.
- Dynamic network which evolves over period of time
- Aggregate network

Definition:

Using dynamic network phenomenon of spread in dynamic spread is being studied. Elements involved in study and assumptions:
- Set of individuals.
- Added dimension is – time. At given time, snapshot of network.
- Series of static networks over period of time.
- All individuals connected to themselves over period of time
- Fixed set of individuals in network at a period of time

Primary difference between aggregate and dynamic networks is element of time.

In aggregate network many permutations will result in the same interactions.

Spreading process:

Spreading process starts with initiator. Here spreading could be anything – disease, social information, advertisements. First they affect their immediate neighbors and same way spreading process continues from neighbor to neighbor

Spreading models:

Two models were studied:
- Independent cascade model
- Linear Threshold model

Independent cascade model: Individuals are either - active (those who are affected) and inactive (not affected by any kind of phenomena spreading)
Probability of influence (Pr)
- Fixed probability assumption
- Potentially every node has different probability of influence

Linear Threshold model: Susceptibility level of the individual (adoption of the new things) Every individual has unique threshold in terms of adapting things (i.e. getting impressed more than others) Model studies groups with inherent threshold for each individual in a group. Connection between two individual has unique threshold. E.g. teacher – student relation has higher threshold.

Assumption: static threshold of 1

Initiator will try to affect neighbor over period of time and pass on the phenomena over particular timestamp. Neighbor based on his/her threshold will try to influence active neighbors. Based on adaptability of neighbors, network will get affected faster vs slower.

Problem statement:

Given: A dynamic network graph
Find: Initial set of individuals
Objective: Maximize the set of individuals who get infected

Influence maximization problem – NP Hard
approximation algorithm: 1-1/e

Greedy approach – keep finding best individual with most influence. Keep refining network picking best case and neighbors and removing them from network.

Experimental approach:

- compare approach with optimal approach (most cases performed equally well)
- compare dynamic vs aggregate (proved that time is crucial component and results vary due to time factor)
o Quantitative comparison
o Qualitative comparison (aggregate network gives inaccurate picture of reality)

Results:

Example of zebras. Recording movement of herds of zebras. Please see presentation for detailed diagrams of network comparing optimal and approximation approaches. Conclusion - Extent of spread varies based on –

- Topology
- Model differences (two models studied gave contradictory results)
- Aggregate network graphs gives inaccurate information and we miss out important information by static approach.