Navigation in Online Social Networks

1. Introduction

In a network of objects, objects can be people or computers, which we refer to them as nodes of the network. Over the course of human history, the collections of social ties among friends have grown steadily in complexity. When people live in neighborhoods or attend schools, the social environment already favors opportunities to form friendships with others like oneself. In the most basic sense, a network is any collection of objects in which some pairs of these objects are connected by links. Have the people in the network adapted their behaviors to become more like their friends, or have they sought out people who were already like them (Easley & Kleinberg, 2011)? (Milgram, 1967) Showed that real world networks are characterized by the small world phenomenon, where any two people in the world are connected through a short chain of acquaintances. The fact that makes Milgram’s original result surprising is that most people tend to move in close social circles tied to a geographical location, profession, or activity.

Many Online Social Networks have user base in the hundreds of millions and a very important factor in navigation of data in such networks is the flow of information. So if we start from any particular node and use the Random Walk model, the information will spread in the network until the flow of information reaches to equilibrium. One of the main problems faced by many researchers is the difficulty of collecting acquaintanceship and related data from human subjects. (Ghosh & Lerman, 2008) claim that a community is composed of individuals who have more influence on individuals within the community than on those outside of it. The more paths there are, the more opportunities one node has to affect the other. They gave a mathematical formulation of influence in terms of the number of paths of any length that link two nodes, and redefined modularity in terms of the influence metric. They use this metric to show how to partition the network into communities.

Authors in (Backstrom, Huttenlocher. & Kleinberg, 2006) have considered the ways in which communities in social networks grow over time, both at the level of individuals and their decisions to join communities, and at a more global level, in which a community can evolve in both membership and content. They consider membership, growth and change in communities. They found that propensity of individuals to join communities, and of communities to grow rapidly, depend in subtle ways on the underlying network structure. To find influential people in an Online Social Network (Ghosh & Lerman, 2010) emphasize the need to distinguish between different dynamic processes occurring in complex networks based on their distinct characteristics. They categorize such processes into conservative and non-conservative, based on the nature of the flow. They classify structural models, which predict the influence standings of actors within a network into conservative and non-conservative models based on the underlying dynamic process that these models emulate. To what extent can the evolution of a social network be modeled using features intrinsic to the network itself?

Authors in (Liben-Nowell, & Kleinberg, 2007) offer a very natural basis for link prediction. They consider common neighbors, similarity and growth. By use of a random predictor, they predict connection between nodes. Authors in (Lattanzi, Panconesi, & Sivakumar, 2011) use affiliation networks and prove that in networks produced by this model, not only do short paths exit among all pairs of nodes but also natural local routing algorithms can discover them effectively. Affiliation network is a bipartite graph with people on one side and interests on the other. The affiliation network comes with an associated friendship graph in which two people are friends if they share an interest. Authors in (Dunn, Gupta, Gerber, & Spatscheck, 2012) compare where users navigate from Online Social Networks versus from search engines. They found out that not only does the outgoing traffic for a major Online Social Network compares with that of a search engine but also Online Social Networks are competing with search engines in their ability to act as conduits between users and websites.