Link Mining in Social Networks

In data mining a social network is a diversion content and multi-relational data set represented by a graph. A graph is very large, with nodes corresponding to objects and edges corresponding to links representing relationships or interactions between objects. Both nodes and links have attributes. Objects may have class labels. Links would be one-directional and are not required to be binary. A key challenge for data mining is tackling the problem of mining richly structured datasets, where the object is linked in some way. Links among the objects can find certain patterns, which may be helpful for many data mining tasks and are typically hard to capture with traditional statistical models. Recently it has been a surge of interest in this area, fueled largely by interest in web and hypertext mining, but also by interest in mining social networks, security and law enforcement data, bibliographic citations and epidemiological records. Traditional data mining tasks such as association rule mining, market basket analysis and cluster analysis commonly attempt to find patterns in a dataset characterized by a collection of independent instances of a single relation. This is consistent with the classical statistical inference problem of trying to identify a model given a random sample from a common underlying distribution. A key challenge for data mining is tackling the problem of mining richly structured, heterogeneous datasets. Naively applying traditional statistical inference procedures, which assume that instances are independent, can lead to inappropriate conclusions. Care must be taken that potential correlations due to links are handled appropriately. In fact, record linkage is knowledge that should be exploited. Clearly, this is information that can be used to improve the predictive accuracy of the learned models: attributes of linked objects are often correlated and links are more likely to exist between objects that have some commonality. Link mining is a newly emerging research area that is at the intersection of the work in link analysis, hypertext and web mining, relational learning and inductive logic programming and graph mining. Link mining is an instance of multi-relational data mining (in its broadest sense); however, we use the term link mining to put an additional emphasis on the links moving them up to first-class citizens in the data analysis endeavor. Link mining encompasses a range of tasks including descriptive and predictive modeling. Both classification and clustering in linked relational domains require new data mining algorithms. But with the introduction of links, new tasks also come to light. Examples include predicting the numbers of links, predicting the type of link between two objects, inferring the existence of a link, inferring the identity of an object, finding co references, and discovering sub graph patterns.