Scalable Learning of Collective Behavior

[attachment=18082]

INTRODUCTION
THE advancement in computing and communication
technologies enables people to get together
and share information in innovative ways. Social
networking sites (a recent phenomenon) empower
people of different ages and backgrounds with new
forms of collaboration, communication, and collective
intelligence. Prodigious numbers of online volunteers
collaboratively write encyclopedia articles of
unprecedented scope and scale; online marketplaces
recommend products by investigating user shopping
behavior and interactions; and political movements
also exploit new forms of engagement and collective
action.


COLLECTIVE BEHAVIOR
Collective behavior refers to the behaviors of individuals
in a social networking environment, but it is not
simply the aggregation of individual behaviors. In a

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication.

connected environment, individuals’ behaviors tend
to be interdependent, influenced by the behavior of
friends. This naturally leads to behavior correlation
between connected users [5]. Take marketing as an
example: if our friends buy something, there is a
better-than-average chance that we will buy it, too.



SOCIAL DIMENSIONS
Connections in social media are not homogeneous.
People can connect to their family, colleagues, college
classmates, or buddies met online. Some relations are
helpful in determining a targeted behavior (category)
while others are not. This relation-type information,
however, is often not readily available in social media.
A direct application of collective inference [9] or label
propagation [12] would treat connections in a social
network as if they were homogeneous. To address
the heterogeneity present in connections, a framework
(SocioDim) [2] has been proposed for collective
behavior learning.


SPARSE SOCIAL DIMENSIONS
In this section, we first show one toy example to
illustrate the intuition of communities in an “edge”
view and then present potential solutions to extract
sparse social dimensions.


4.1 Communities in an Edge-Centric View
Though SocioDim with soft clustering for social dimension
extraction demonstrated promising results,
its scalability is limited.


Edge Partition via Line Graph Partition
In order to partition edges into disjoint sets, one way
is to look at the “dual” view of a network, i.e., the line
graph [15]. We will show that this is not a practical
solution. In a line graph L(G), each node corresponds
to an edge in the original network G, and edges in
the line graph represent the adjacency between two
edges in the original graph. The line graph of the toy
example is shown in Figure 4. For instance, e(1, 3) and
e(2, 3) are connected in the line graph as they share
one terminal node 3.