P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38
2
Graph Essentials
We live in a connected world in which networks are intertwined with our
daily life. Networks of air and land transportation help us reach our destina-
tions; critical infrastructure networks that distribute water and electricity are
essential for our society and economy to function; and networks of commu-
nication help disseminate information at an unprecedented rate. Finally, our
social interactions formsocial networksof friends, family, and colleagues.
Social media attests to the growing body of these social networks in which
individuals interact with one another through friendships, email, blogposts,
buying similar products, and many other mechanisms.
Social media mining aims to make sense of these individuals embedded
in networks. These connected networks can be conveniently represented
using graphs. As an example, consider a set of individuals on a social
networking site where we want to find the most influential individual. Each
individual can be represented using anode(circle) and two individuals who
know each other can be connected with anedge(line). In Figure2.1,we
show a set of seven individuals and their friendships. Consider a hypothetical
social theory that states that “the more individuals you know, the more
influential you are.” This theory in our graph translates to the individual with
the maximumdegree(the number of edges connected to its corresponding
node) being the most influential person. Therefore, in this networkJuanis
the most influential individual because he knows four others, which is more
than anyone else. This simple scenario is an instance of many problems
that arise in social media, which can be solved by modeling the problem
as a graph. This chapter formally details the essentials required for using
graphs and the fundamental algorithms required to explore these graphs in
social media mining.