Proceedings of the VLDB Endowment · 2018 · 66 citations · 33 references
ComputingComputer ScienceData MiningInformation RetrievalSocial InfluenceCommunity DetectionCommunity StructureGraph AlgorithmsNetwork CentralitySearching AlgorithmsSocial Network AnalysisGraph IndexingGraph SearchNetwork GraphsOnline SearchSubgraph CentralitySubgraph ExtractionSubgraph Mining
Community search over large graphs is a fundamental problem in graph analysis. Recent studies propose to compute top- k influential communities, where each reported community not only is a cohesive subgraph but also has a high influence value. The existing approaches to the problem of top- k influential community search can be categorized as index-based algorithms and online search algorithms without indexes. The index-based algorithms, although being very efficient in conducting community searches, need to pre-compute a special-purpose index and only work for one built-in vertex weight vector. In this paper, we investigate online search approaches and propose an instance-optimal algorithm LocalSearch whose time complexity is linearly proportional to the size of the smallest subgraph that a correct algorithm needs to access without indexes. In addition, we also propose techniques to make LocalSearch progressively compute and report the communities in decreasing influence value order such that k does not need to be specified. Moreover, we extend our framework to the general case of top- k influential community search regarding other cohesiveness measures. Extensive empirical studies on real graphs demonstrate that our algorithms outperform the existing online search algorithms by several orders of magnitude.
33
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text
On Spectral Clustering: Analysis and an algorithm
Andrew Y. Ng, Michael I. Jordan, Yair Weiss · 2001 · 7.8K citations
Algebraic connectivity of graphs
Miroslav Fiedler · Czechoslovak Mathematical Journal · 1973 · 4K citations · Full text
Network structure and minimum degree
Stephen B. Seidman · Social Networks · 1983 · 1.9K citations