From Frequent Features to Frequent Social Links

摘要

Standard data mining techniques have been applied and adapted for eliciting knowledge from social networks, by achieving classical tasks such as classification, search for frequent patterns or link prediction. Most works have exploited only the network topological structure, and therefore cannot be used to answer questions involving nodes features. For instance, the frequent pattern discovery task generally refers to the search for sub-networks frequently found in a single network or in a set of networks. In the same area, this paper focuses on the concept of frequent link that stands as a regularity found in a network on links between node groups that share common characteristics. The extraction of such links from a social network is a particularly challenging and computationally intensive problem, since it is much dependent on the number of links and attributes. In this study, the authors propose a solution for reducing the search space of frequent links, by filtering the nodes features on a criterion of frequency. The authors make the assumption that frequent links occur between sets of features that are themselves frequent. This property is used to reduce the search space and speed up the extraction process. The authors empirically show that it is well founded, and they discuss the efficiency of the solution in terms of computation time and number of frequent patterns found depending on several frequency thresholds.