Structural search and optimization in social networks (Q2815472)

This paper studies structural search and optimization in social networks. Two problems called the elite group problem and the portal problem are introduced based on the two set notations: influential sets and central sets. Given a directed graph \(G(V,E)\), an elite group is a set \(W\subseteq V\) such that there does not exist a directed edge \((i,j)\in E\) with \(i\in W\) and \(j\not\in W\). The elite group problem aims to maximize the total number of directed edges incident on the nodes in \(W\). It is shown that this problem is polynomially solvable. If a size-constrained elite group is considered, then the decision problem associated is strongly \(NP\)-complete. Given a connected but undirected graph \(G(V,E)\) and a positive integer \(k\), the portal problem looks to maximize the measure \(r(Q)\) such that \(Q\in V\) and \(|Q|\le k\). Here, \(r(Q)\) is the normalized between centrality of \(Q\) by the quantity \(\binom{n-|Q|}{2}\) and \(n\) is the graph order. The decision problem associated to the portal problem is strongly \(NP\)-complete. The paper also discussed the portal problem in bi-cliques, balanced and full \(d\)-trees, paths, as well as cycles.