public class SocialNetwork extends WeightedGraph<Actor> implements NetworkOfActivatables<Actor>
This class represents a social network as a directed graph
of individual nodes represented by actors
.
In usual diffusion models such as the “Linear Threshold model”
for the spread of an idea, an innovation, or a disease through a social network,
each individual actor is either active (e.g., an adopter of the innovation)
or inactive.
An inactive actor is activated if the influence of its incident neighbors,
each given by corresponding weighted edges, in sum outvalue its threshold.
Usually, the thresholds are chosen at random according to some specified distribution
function.
Given an initial set of active actors (with all other actors inactive),
the diffusion process unfolds deterministically in discrete steps:
in step t, all actors that were active in step t–1 remain active,
and any actor i is activated for which the total sum of the normalized weights
wji of its active neighbors
is at least its threshold θi:
|
wji | ≥ | θi |
The threshold θi therefore intuitively represents the different latent tendencies of actors to get become active (e.g., to adopt the innovation or to be infected by a disease) when their contacts do. The process stops if no more activations are possible.
Based on physical theories on interacting particle systems, the “Independent Cascade Model“ also starts with an initial set of active actors, but the process now unfolds in discrete steps according to the randomized rule that an actor i first becomes active in step t it has only a single chance to activate each currently inactive neighbor j and succeeds with probability wij, independently of the history so far. In other words, actor j is activated is activated by i in step t+1 with probability wij. Again, the process runs until no more activations are possible.
The influence maximization problem asks, for a parameter k, to find a set A0 of k initially active actors which has maximum influence. For both the linear threshold model and the independant cascade model, the influence maximization problem is NP-hard.
For more details and further references, see D. Kempe, J. Kleinberg & E. Tardos: ’Maximizing the Spread of Influence through a Social Network‘, Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining. 2003, as well as F. Morone, H.A. Makse (2015): ‘Influence maximization in complex networks through optimal percolation’, Nature 524 (7563), pp. 65–68, doi 10.1038/nature14604 (or preprint arxiv 1506.08326).
Modifier and Type | Field and Description |
---|---|
protected boolean |
active
Flag which shows if there has been an active actor during the history of this network.
|
DF, dist, distance, INFINITY, next, pred, weight
adjacency, modifiableHashimoto, numberOfEdges, relevance, SEPARATOR, undirected, vertices, weighted
Constructor and Description |
---|
SocialNetwork(Actor[] actors,
double[][] weights)
Creates a social network of the specified actors and their directed and weighted
relations determined by the specified weight matrix.
|
SocialNetwork(Actor[] actors,
int[][] adjacency)
Creates a social network of the specified actors and their directed
relations determined by the specified adjacency matrix.
|
SocialNetwork(boolean undirected,
Actor[] actors,
double[][] weights)
Creates a social network of the specified actors and their
relations determined by the specified flag whether they are symmetric
and by the specified weight matrix.
|
SocialNetwork(boolean undirected,
Actor[] actors,
int[][] adjacency)
Creates a social network of the specified actors and their
relations determined by the specified flag whether they are symmetric
and by the specified adjacency matrix.
|
Modifier and Type | Method and Description |
---|---|
HashSet<Actor> |
activate(Actor... actors)
Activates all actives specified by the input actors, i.e.,
marks each of them as active.
|
HashSet<Actor> |
activate(Collection<Actor> actors)
Activates all actives specified by the input set of actors, i.e.,
marks each of them as active.
|
static SocialNetwork |
createNetworkFromCSVFile()
Creates a social network from a CSV file selected by a file chooser dialog.
|
HashSet<Actor> |
deactivate(Actor... actors)
Deactivates all actors specified by the input actors, i.e.,
marks each of them as inactive.
|
HashSet<Actor> |
deactivate(Collection<Actor> actors)
Deactivates all actors specified by the input set of actors, i.e.,
marks each of them as inactive.
|
boolean |
isActive()
Returns at least one of the nodes has been active during the history
of this network.
|
HashSet<Actor> |
nextActivationStep(HashSet<Actor> activeGeneration)
Returns the actors activated by the specified active generation of actors
in this social network, after a single activation step according to the
linear threshold model.
|
HashSet<Actor> |
runActivation(HashSet<Actor> initiators)
Returns the actors finally activated by the specified active initiators
in this social network, according to the linear threshold model.
|
void |
setActive(boolean active)
Sets this network as active, i.e., it has had at least one of its nodes
been active during the history of this network.
|
bellmanFord, create, createWeightedGraph, createWeightedGraphFromCSVFile, dijkstra, floydWarshall, getWeight, show, toCSV, toString
breadthFirstSearch, collectEdges, computeHashimoto, computeNumberOfEdges, createGraph, createGraphFromCSVFile, depthFirstSearch, depthFirstSearch, detectClusters, detectClustersExactly, getAdjacency, getComponents, getCycles, getDegree, getDegree, getDegrees, getIndegree, getIndegree, getIndegrees, getModifiedHashimoto, getNumberOfEdges, getOutdegree, getOutdegree, getOutdegrees, getRelevance, getRelevanceClusters, getVertex, getVertices, hasCycles, isUndirected, laplacian, main, saveAsCSV, setUndirected, setVertices, subgraph, subgraph, toHTMLString, toJTable, topologicalSort
protected boolean active
public SocialNetwork(Actor[] actors, double[][] weights)
actors
- an array of the actors forming this social networkweights
- the weight matrix determining the relations between the actorspublic SocialNetwork(Actor[] actors, int[][] adjacency)
actors
- an array of the actors forming this social networkadjacency
- the adjacency matrix determining the relations between the actorspublic SocialNetwork(boolean undirected, Actor[] actors, double[][] weights)
undirected
- flag whether this social network is undirectedactors
- an array of the actors forming this social networkweights
- the weight matrix determining the relations between the actorspublic SocialNetwork(boolean undirected, Actor[] actors, int[][] adjacency)
undirected
- flag whether this social network is undirectedactors
- an array of the actors forming this social networkadjacency
- the adjacency matrix determining the relations between the actorspublic boolean isActive()
isActive
in interface NetworkOfActivatables<Actor>
public void setActive(boolean active)
setActive
in interface NetworkOfActivatables<Actor>
active
- true if and only if a node of this network has been activepublic HashSet<Actor> activate(Actor... actors)
actors
- a set actors of this network to be activatedpublic HashSet<Actor> activate(Collection<Actor> actors)
actors
- a set actors of this network to be activatedpublic HashSet<Actor> deactivate(Actor... actors)
actors
- a set actors of this network to be activatedpublic HashSet<Actor> deactivate(Collection<Actor> actors)
actors
- a set actors of this network to be activatedpublic HashSet<Actor> runActivation(HashSet<Actor> initiators)
runActivation
in interface NetworkOfActivatables<Actor>
initiators
- an array of activated actors of this network.
This methods marks each of them as active.public HashSet<Actor> nextActivationStep(HashSet<Actor> activeGeneration)
nextActivationStep
in interface NetworkOfActivatables<Actor>
activeGeneration
- a list of activated actors of this network.
This methods marks each of them as active.public static SocialNetwork createNetworkFromCSVFile()
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective weight matrix entry
weight[i][j]
is expected to have the value
Double.POSITIVE_INFINITY
, 0
, or an empty string.
The vertices of the returned graph are of the raw type Actor
.