Efficient s-Core Community Search on Attributed Graphs

With the advantage of high personalization in many applications,com-munity search on attributed graphs has received increasing attention.The com-munities found in an attributed graph,called attributed communities,show inher-ent community structure and attribute cohesion.However,most of the traditional community search algorithms only consider the existence of query attributes in the resulting communities,which ignores the importance of attribute quantities.In this paper,we study the attributed community search problem and formu-late this problem asfinding the tightest connected subgraph,named the s-core attributed community,that meets the given query condition.We introduce an effi-cient algorithm using local search and attribute inspection techniques to search the communities.Additionally,pruning techniques that exploit community struc-ture and attribute information are proposed to prevent unnecessary community construction and attribute inspection.Finally,we conduct extensive experiments on real-world datasets.The experimental results verified the pruning strategy’s effectiveness and the algorithm’s efficiency.