Local community finding algorithms are helpful for finding communities around a seed node especially when the network is large and a global method is too slow. Most local methods find only a single community or are required to be run several times over different seed nodes to create multiple communities. In this paper, we present a new algorithm, LCHI that finds multiple, overlapping communities around a single node. Examples and analyses are presented support the effectiveness of LCHI.

This paper presents the community set space canvas, a triangular canvas where the results of community finding algorithms can be plotted for comparison. The points of the triangle represent trivial sets, such as the set of one large community, and the edges are populated by well known set types, such as disjoint communities.

Within networks there is often a pattern to the way nodes link to one another. It has been shown that the accuracy of node classification can be improved by using the link data. One of the challenges to integrating the attribute and link data, though, is balancing the influence that each has on the classification decision. In this paper we present a matrix alignment approach to the problem of collective classification which weights the attributes and the links according to their predictive influence. The experiments show that while our approach provides comparable accuracy in prediction to other methods, it is also very fast and descriptive.

Social networks have become a major focus of research in recent years, initially directed towards static networks but increasingly, towards dynamic ones. In this paper, we investigate how different pre-processing decisions and different network forces such as selection and influence affect the modeling of dynamic networks. We also present empirical justification for some of the modeling assumptions made in dynamic network analysis (e.g., first-order Markovian assumption) and develop metrics to measure the alignment between links and attributes under different strategies of using the historical network data. We also demonstrate the effect of attribute drift, that is, the importance of individual attributes in forming links change over time.

This paper introduces a new discriminative learning technique for link prediction based on the matrix alignment approach. Our algorithm automatically determines the most predictive features of the link structure by aligning the adjacency matrix of a network with weighted similarity matrices computed from node attributes and neighborhood topological features. Experimental results on a variety of network data have demonstrated the effectiveness of this approach.

Social bookmarking tools enable users to save URLs for future reference, to create tags for annotating Web pages, and to share Web pages they found interesting with others. This paper presents a case study on the application of link mining to a social bookmarking Web site called del.icio.us. We investigated the user bookmarking and tagging behaviors and described several approaches to find surprising patterns in the data. We also identified the characteristics that made certain users more popular than others. Finally, we demonstrated the effectiveness of using social bookmarks and tags for predicting mutual ties between users.

Communities are nodes in a network that are grouped together based on a common set of properties. While the communities and link structures are often thought to be in alignment, it may not be the case when the communities are defined using other external criterion. In this paper we provide a new way to measure the alignment. We also provide a new metric that can be used to estimate the number of communities to which a node is attached. This metric, along with degree, is used to assign a community-based role to nodes. We demonstrate the usefulness of the community-based node roles by applying them to the influence maximization problem.

In this paper, we study the ill-effects of bridgenodes, which causes many dissimilar objects to be placed together in the same cluster by existing clustering algorithms. We offer two new metrics for measuring how well a clustering algorithm handles the presence of bridge-nodes. We also illustrate how algorithms that produce overlapping clusters help to alleviate the effect of bridge-nodes and form more meaningful clusters. However, if there is too much overlap, the clusters become less informative. To address this problem, we present a novel clustering algorithm called MIN-CUT. Our experimental results with real data sets show that the MIN-CUT algorithm leads to purer clusters that have very little overlap.