Design And Implementation Of Community Search Algorithms In Social Networks

Many of the information in the real world exists in the form of networks,such as interpersonal relations networks,protein webs in biology,cooperative networks in essay writing,and so on.Community structure is an important feature in complex networks.It can reveal the hidden patterns and behavioral features of social networks.After the community detection problems closely related to the community structure have been proposed,they become the research hotspots of domestic and foreign scholars.The community search problems that are related to community detection but are not the same are the problems studied in this paper.Community search is to enter a graph,a query vertex,and then find an intensive subgraph containing this query node.The topic of this paper is to design and implement a community search system in a social network.The system mainly implements:The first kind of community search in non-attribute graph is based on the density of triangle-graph.In this paper,we introduce a new method for discovering communities based on triangle-graph densest subgraph(TGDS).Given an input graph,its triangle is a new graph constructed from the input graph,where each vertex of the new graph corresponds to a triangle of the input graph,and if the input graph has two triangles sharing the same edge,then the new there is one edge between two vertices in the graph.We have defined a simple density function,the density of a triangular graph,which will give a dense subgraph,which is the community we want.The second is community search based on vertex keywords in attribute graphs.In this chapter,we propose an attribute score function to calculate the attribute scores of each vertex in the graph,and then input a graph,a query node and a set of query properties.A subgraph containing the query node and the attributes of this node will be obtained,and the attributes of each node in this subgraph are the same as the attributes of the query node.Then,based on the attribute score of each vertex calculated in the previous step,the node with less attribute scores in the obtained subgraph is deleted.The resulting subgraph is the community we need.