Network Performance Aware Graph Partitioning for Large Graph Processing Systems in the Cloud - Large Scale and Big Data: Processing and Management - page 230

completeness of discussions, Section 7.7 gives an introduction to existing graph partition-
ing approaches, although they may not be related to the cloud technologies. A discussion
of open problems is provided in Section 7.8. We summarize the chapter in Section 7.9.
7.2 APPLICATIONS OF LARGE GRAPHS
Large graphs have arisen in a wide range of data-intensive applications. To begin our
discussions, we first describe a small and non-exhaustive set of typical examples of
large graphs and their applications.
7.2.1 s oCial n etworks
In social networks, nodes often represent users and edges may often represent rela-
tionships between users (friendships). Today, there are plenty of large social net-
works. For example, the social network of Facebook consisted of 1 billion nodes
and more than 100 billion edges in 2012 [70]. The largest publicly available social
network (contributed by Yahoo!*) consists of more than 1 billion nodes. The social
network of LinkedIn contained almost 218 million nodes in the first quarter of 2013 [54].
The project FlockDB manages social graphs with more than 13 billion edges [40].
Moreover, social networks are evolving at an unprecedented rate. For example, it has
been reported that, between 2004 and 2012, the Facebook network increased from
roughly 1 million to 1 billion users [70].
Analysis on social networks has become a hot research topic. Work has been con-
ducted identifying and searching user communities from the networks, and studies have
been carried out to estimate the diameter and the radius of a network (e.g., [42]). These
studies show how users are connected and indicate which users are outliers of the net-
work. It is reported that the small-world phenomenon has been found in social networks
[42]. In practice, despite the large number of users on social networks, it is often a user's
close friends who often have the most influence on him/her. It is desirable to determine
two- or three-hop friend lists for a social network user. Another application of the net-
works is to help organizing activities. An organizer can find not only a group of his/her
close friends, but also groups that contain people who are close friends of each other.
7.2.2 w eb g raPhs
Another example of large graphs is the WWW graph. The nodes represent web
pages and edges represent hyperlinks. Google estimates that there are over 1 tril-
lion web pages. The indexed web contained at least 4.6 billion web pages as of June
2013. † Today, the WWW graphs for experimentation contain more than 20 billion
web pages and 160 billion hyperlinks. The web page hyperlink connectivity graph
of Yahoo! AltaVista of 2002 is publicly available. ‡ The well-known application of
* Webscope from Yahoo! Labs. Graph, and Social Data. http://webscope.sandbox.yahoo.com/catalog.
php?datatype=g.
† WorldWideWebSize.com: http://www.worldwidewebsize.com/.
‡ Webscope from Yahoo! Labs. Graph and Social Data. http://webscope.sandbox.yahoo.com/catalog.
php?datatype=g.