Structural Search and Optimization in Social Networks

DSpace/Manakin Repository

Structural Search and Optimization in Social Networks

Show full item record

Title: Structural Search and Optimization in Social Networks
Author(s):
Dawande, Milind W.;
Mookerjee, Vijay S.;
Sriskandarajah, Chelliah;
Zhu, Yunxia
Date Created: 2011-05
Format: text
Item Type: article
Keywords: Online algorithms
Computational complexity
Social networks
Database searching
Abstract: The explosive growth in the variety and size of social networks has focused attention on searching these networks for useful structures. Like the Internet or the telephone network, the ability to efficiently search large social networks will play an important role in the extent of their use by individuals and organizations alike. However, unlike these domains, search on social networks is likely to involve measures that require a set of individuals to collectively satisfy some skill requirement or be tightly related to each other via some underlying social property of interest. The aim of this paper is to highlight-and demonstrate via specific examples-the need for algorithmic results for some fundamental set-based notions on which search in social networks is expected to be prevalent. To this end, we argue that the concepts of an influential set and a central set that highlight, respectively, the specific role and the specific location of a set are likely to be useful in practice. We formulate two specific search problems: the elite group problem (EGP) and the portal problem (PP), that represent these two concepts and provide a variety of algorithmic results. We first demonstrate the relevance of EGP and PP across a variety of social networks reported in the literature. For simple networks (e.g., structured trees and bipartite graphs, cycles, paths), we show that an optimal solution to both EGP and PP is easy to obtain. Next, we show that EGP is polynomially solvable on a general graph, whereas PP is strongly NP-hard. Motivated by practical considerations, we also discuss (i) a size-constrained variant of EGP together with its penalty-based relaxation and (ii) the solution of PP on balanced and full d-trees and general trees. © 2012 INFORMS.
ISSN: 1091-9856
Persistent Link: http://dx.doi.org/10.1287/ijoc.1110.0473
http://hdl.handle.net/10735.1/3203
Terms of Use: © 2012 INFORMS

Files in this item

Files Size Format View
SOM-FR-Mookerjee-310502.98.pdf 553.5Kb PDF View/Open

This item appears in the following Collection(s)


Show full item record