Navigation in Online Social Networks

Navigation in Online Social Networks

Mehran Asadi, Afrand Agah
DOI: 10.4018/978-1-4666-8505-5.ch016
(Individual Chapters)
No Current Special Offers


In this chapter, we investigate the role of influential people in an Online Social Network. We introduce a navigation approach to locate influential nodes in Online Social Networks. The purpose of quantifying influence in Online Social Networks is to determine influence within the members of an Online Social Networks and then using influence for navigation in such networks. We find out that we can take advantage of influential people in Online Social Networks to reach a target node in such networks. We utilize total number of direct friends of each node, total number of shared neighbors, the total number of common attributes, the total number of unique attributes, the distance to target node, and past visited nodes. We present an algorithm that takes advantage of influential people to reach a target in the network. Our navigation algorithm returns a path between two nodes in an average of ten percent less iterations, with a maximum of eighty percent less iterations, and only relies on public attributes of a node in the network.
Chapter Preview

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.

Key Terms in this Chapter

Neighboring Nodes: Nodes in a network that share a link.

Attributes: A predefined set of properties of a node in a network.

Online Social Networks: When people interact with each other over the Internet.

Node Similarities: Common attributes among different nodes.

Web Crawlers: Algorithms that are being used to do navigation on a network.

Influence: The ability of persuading people to do an action.

Navigation: Staring from one source node in a network and traversing different paths in order to reach to a specific destination node.

Complete Chapter List

Search this Book: