Structural Search and Optimization in Social Networks

dc.contributor.ISNI0000 0000 9095 8730 (Sriskandarajah, C)
dc.contributor.LCNA2010125665 (Sriskandarajah, C)
dc.contributor.LCNA90649574‏ (Mookerjee, VS)
dc.contributor.authorDawande, Milind W.en_US
dc.contributor.authorMookerjee, Vijay S.en_US
dc.contributor.authorSriskandarajah, Chelliahen_US
dc.contributor.authorZhu, Yunxiaen_US
dc.description.abstractThe 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.en_US
dc.identifier.bibliographicCitationDawande, M., V. Mookerjee, C. Sriskandarajah, and Y. Zhu. 2012. "Structural search and optimization in social networks." INFORMS Journal on Computing 24(4): 611-623.en_US
dc.rights© 2012 INFORMSen_US
dc.source.journalINFORMS Journal on Computingen_US
dc.subjectOnline algorithmsen_US
dc.subjectComputational complexityen_US
dc.subjectSocial networksen_US
dc.subjectDatabase searchingen_US
dc.titleStructural Search and Optimization in Social Networksen_US


Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
553.58 KB
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Informs Online.pdf
223.09 KB
Adobe Portable Document Format