Database Reference
In-Depth Information
time. Therefore, a key challenge is to determine such communities in dy-
namic networks, when the clustering patterns may change significantly
over time. Methods for determining evolving clusters and communities
in networks have been discussed in [10, 12, 31, 28, 79, 151]. Many of
these methods determine communities in the underlying data by incor-
porating concepts of
temporal smoothness
, wherein the structure of the
communities is allowed to evolve only in a smooth way over time. On
the other hand, when the data is of very high volume (such as a graph
stream), it is also critical to design very ecient methods for commu-
nity maintenance. Graph streams pose a special challenge because of
the rapid nature of the incoming edges, and their use for determination
of evolving communities.
(2) Mining Structural Patterns in Time-Evolving Social Net-
works:
Aside from the common problem of community detection, an-
other interesting problem is that of mining structural patterns of differ-
ent kinds in time evolving graphs. Some common methods for finding
such patterns typically use matrix and tensor-based tools, which are
comprehensively described in a tutorial in [60]. Common problems in
time-evolving graphs include those of frequent pattern determination,
outlier detection, proximity tracking [156], and subgraph change detec-
tion [118].
(3) Modeling spatio-temporal dynamics:
Many of the approaches
discussed above model the dynamics of the interactions as dynamic links.
While this provides greater generality, it does not capture the spatio-
temporal nature of the underlying agents. For example, the data re-
ceived in a GPS application often contains spatio-temporal information
such as the positions of different agents, and their underlying interac-
tions. Therefore, an interesting and important challenge is to model the
aggregate spatio-temporal dynamics in order to determine the underly-
ing patterns and clusters. Such spatio-temporal dynamics can be used
in order to make interesting
spatial predictions
such as future regions
of activity or congestions. Many methods for clustering, community
detection, classification, and outlier detection from such data have been
proposed in [104, 105, 112-115, 109, 110] and are discussed in some detail
in the application section of this chapter. In many cases, such data may
even be combined with other content-based data such as GPS-tagged
images and documents in order to further improve the quality of the
underlying inference [172].
(4) Modeling Influential Community Members:
This problem is
essentially that of determining the members of the participatory sensor
network, who have the greatest influence on their peers in the commu-
nity. Alternatively, it may also be interesting to trace back the spread of
