Study On Topic-aware Spatial-optimal Community Search Algorithms

Attributed networks are prevalent,e.g.social and knowledge graphs,which are associated with massive documents(e.g.,tweets and wiki pages)and locations(e.g.,check-ins).The rich attributes of such large networks pose great challenges to community search due to the scalability issues in addition to the dual query constraints on both textual and spatial extent.The existing studies,aiming to find dense subgraphs yielding socially close communities,often lack the consideration on either keywords indicating topic-aware interests or spatial distance showing preference within vicinity.We propose a topic-aware spatial-optimal community(TaSoC)search problem,which returns a community that has the following properties:i)structural cohesiveness:members are densely connected,ii)topic cover:a set of keywords are contained by vertex attributes,and iii)spatial optimality:the diameter of the community is minimized.The TASOC problem is shown to be NP-hard.To solve the problem on large attributed networks,we develop 4 approximation algorithms,i.e.,GKC,GRID,BIGRID and GRID+.They all utilize a technique designed in terms of squares.These methods are proved to be more efficient than the adapted baseline methods.An exact solution based on the best approximate algorithm is also developed in order to achieve good performance with optimal results on relatively small graphs.The extensive experiments conducted on both real and synthetic datasets(5 datasets in total)demonstrate the efficiency and effectiveness of the proposed scheme.It is also shown that the approximation algorithms are much faster than the exact solution yet with high accuracy.