The problem discussed in this paper is in fact linked to social media and network research. Social media, as it is well known, offers opportunities for commerce and other business activities. The paper refers to examples in advertising, viral marketing, recommendation (tourism, content, and so on), and even team formation.
To understand the contribution of the paper and the basic principles that are delineated, the reader needs a strong background either in mathematics or computing science. On using the language of mathematics, the task is to find a connected subgraph within a graph that is a representation of relationships in a community. This subgraph has some favorable properties; that is, it contains all query vertices and maximizes the minimum degree. A query vertex (or node) represents a query over incident edges from the perspective of a vertex; the query generally exploits a “tricky” or appropriate edge labeling mechanism that speeds up the information retrieval. The minimum degree is a good metric for measuring the “goodness of community” as it is proved by previous research. The paper contains an extensive literature overview that analyzes the drawbacks of the recent algorithms to find the appropriate connected subgraph that contains the query vertices.
For this reason, the proposed approach is a heuristic, greedy algorithm that improves the efficiency, effectiveness, and generality beyond the level of the existing methods. The paper proves some theorems related to the proposed algorithm and the community-search problem (CSP); its understanding requires profound graph-theoretic knowledge. The paper outlines the basic compounds of the algorithm in pseudocode format.
Aside from the theoretical results, the experiments that were carried out by the proposed algorithm are described along with the statistical reports. The statistics are analyzed to underpin the statement that the proposed algorithm yields better values regarding efficiency and effectiveness.
To compare the proposed algorithm to other ones in the literature, the authors selected well-known and widely accepted measures for the quality of communities discovered in graphs. These measures are the size, the density, and the query-biased density of communities that have been found in the investigated graphs. For every experiment, a sample of query vertices is selected randomly. The results of experiments are averaged over this set of query vertices and on the previously mentioned measurements. To prove the statistical soundness of the pursued procedure, the statistical significance of the applied methods is calculated; moreover, the p-values are computed as well.
The paper is interesting for researchers of social networks and graph algorithms. In the research and development fields, the algorithm may be exploited for business applications.