7.3. Summary
95
Notes
Temporal (dynamic) social network analysis aims to understand the structures in networks as they evolve, building on static analysis techniques but including variation.
There are two different ways of framing the problem which have led to two different
algorithmic strategies.
The first might be called the “Networks only change slowly” view. Recomputing a spectral embedding after every network change is expensive, especially for
large networks. It is more efficient to update the current network structure from the
(assumed small) changes that have taken place. For example, Shang et al. [82, 83]
keep track of the community structure of temporal networks by using an extended
modularity algorithm based on the Newman algorithm. Nguyen et al. [72] update
the network structure based on new-Node, remove-Node, new-Edge, remove-Edge
primitives. Bouchachia and Prossegger [9] extend the spectral approach with fuzzy
c-varieties to cluster incremental data. Aston and Hu [2] update the community
structure based on a density-based clustering algorithm. Kas et al. [44] propose an
incremental algorithm by updating the affected parts only.
Even a small change in the network can produce a large change in the embedded structure, but these approaches implicitly assume that this does not happen.
Finding matching reference points from one embedding to the next is also non-trivial,
but again the implicit assumption is that changes have been small enough to enable
some level of tracking across time.
The second framing might be called the “Align the independent networks”
view. These approaches treat each network at a moment in time independently, but
try to get the structures of the network into a consistent form. For example, Qiu and
Lin [77] explore the evolution of the organizational structure of a temporal network
by comparing the change to the evolving community trees based on random walk
and PageRank. Gong et al. [36] propose a novel multi-objective immune algorithm
to cluster temporal networks into consistent communities. Yang et al. [109] analyze
the community evolution based on a statistical model. However, these approaches
only consider the evolution of each network at the level of group structures, and fail
to handle changing properties of individual nodes and edges.
The approach in this chapter was described in Skillicorn, Zheng, and Morselli
[89, 90].
95
Notes
Temporal (dynamic) social network analysis aims to understand the structures in networks as they evolve, building on static analysis techniques but including variation.
There are two different ways of framing the problem which have led to two different
algorithmic strategies.
The first might be called the “Networks only change slowly” view. Recomputing a spectral embedding after every network change is expensive, especially for
large networks. It is more efficient to update the current network structure from the
(assumed small) changes that have taken place. For example, Shang et al. [82, 83]
keep track of the community structure of temporal networks by using an extended
modularity algorithm based on the Newman algorithm. Nguyen et al. [72] update
the network structure based on new-Node, remove-Node, new-Edge, remove-Edge
primitives. Bouchachia and Prossegger [9] extend the spectral approach with fuzzy
c-varieties to cluster incremental data. Aston and Hu [2] update the community
structure based on a density-based clustering algorithm. Kas et al. [44] propose an
incremental algorithm by updating the affected parts only.
Even a small change in the network can produce a large change in the embedded structure, but these approaches implicitly assume that this does not happen.
Finding matching reference points from one embedding to the next is also non-trivial,
but again the implicit assumption is that changes have been small enough to enable
some level of tracking across time.
The second framing might be called the “Align the independent networks”
view. These approaches treat each network at a moment in time independently, but
try to get the structures of the network into a consistent form. For example, Qiu and
Lin [77] explore the evolution of the organizational structure of a temporal network
by comparing the change to the evolving community trees based on random walk
and PageRank. Gong et al. [36] propose a novel multi-objective immune algorithm
to cluster temporal networks into consistent communities. Yang et al. [109] analyze
the community evolution based on a statistical model. However, these approaches
only consider the evolution of each network at the level of group structures, and fail
to handle changing properties of individual nodes and edges.
The approach in this chapter was described in Skillicorn, Zheng, and Morselli
[89, 90].