Semi-Supervised Graph Pattern Matching and Rematching for Expert Community Location

摘要

Graph pattern matching (GPM) is widely used in social network analysis, such as expert finding, social group query, and social position detection. Technically, GPM is to find matched subgraphs that meet the requirements of pattern graphs in big social networks. In the application of expert community location, the nodes in the pattern graph and data graph represent expert entities, and the edges represent previous cooperations between them. However, the existing GPM methods focus on shortening the matching time and without considering the preference of the decision maker (DM), which makes it difficult for the DM to find ideal teams from numerous matches to complete the assigned task. In this article, as for the process of graph pattern matching and rematching, with a preferred expert set, i.e., the DM hopes that one or more experts in this set will appear in matched subgraphs, we propose a Dual Simulation-based Edge Sequencing-oriented Semi-Supervised GPM method (DsEs-ssGPM). In addition, considering a preferred expert set and a dispreferred expert set together, the DM hopes that experts in the dispreferred expert set will not appear in final matches, so we have the DsEs-ssGPM+ method. Technically, these DsEs-ssGPM methods conduct the matching process from the preferred expert set during dual simulation-based edge sequencing, and based on the edge sequence, these edges are searched recursively. Especially, as for the rematching process, when the preferred and/or the dispreferred expert sets change continuously, to process the GPM again is unnecessary and it is possible to revise the previous matched results partially with DsEs-ssGPM methods. Experiments on four large datasets demonstrate the effectiveness, efficiency and stability of our proposed DsEs-ssGPM methods, and the necessity of introducing an edge sequencing mechanism.