Keyword Aware Influential Community Search in Large Attributed Graphs
Table 4: Structural cohesiveness measures
['Dataset', 'Density', 'Average Degree', 'Clustering Coefficient', 'Diameter']
Structural cohesiveness: We use popular structural cohesiveness metrics diameter, density, average degree, and clustering coefficient [Fang2019] to measure the quality of the communities retrieved by our approach. These measures mostly depend on the community models (e.g., k-core, k-truss) as discussed in a survey of community search [Fang2019]. They prefer the k-core model because of its high efficiency with minimal sacrifice in structural cohesiveness. We conduct experiments on Gowalla dataset to show that our algorithms can handle large number (millions) of keywords. We also compare the effectiveness and efficiency of the communities retrieved by our approach, and Li et al. [li2015influential]. The query setup and parameter settings are done in the same way as in the OAG dataset. The number of relevant vertices is very small for queries in this dataset. The average query processing time is around 2 ms for all the algorithms. However, our key observation is that unlike OAG, in a dataset where connectivity is not related to keywords, the Online-All fails to address the keyword cohesiveness of the communities, while our approach returns communities considering both structural and keyword cohesiveness. The results show that our approach returns communities with significantly higher (approx. 15 and 5 times for AND and OR predicate respectively) keyword cohesiveness than the Online-All.