Node roles and community structure in networks

ABSTRACT

A node role is a subjective characterization of the part it plays in a network structure. Knowing the role of a node is important for many link mining applications. For example, in Web search, nodes that are deemed to be authorities on a given topic are often found to be most relevant to the user's queries. There are a number of metrics that can be used to assign roles to individual nodes in a network, including degree, closeness, and betweenness. None of these metrics, however, take into account the community structure that underlies the network. In this paper we define community-based roles that the nodes can assume (ambassadors, big fish, loners, and bridges) and show how existing link mining techniques can be improved by knowledge of such roles. A new community-based metric is introduced for estimating the number of communities linked to a node. Using this metric and a modification of degree, we show how to assign community-based roles to the nodes. We also illustrate the benefits of knowing the community-based node roles in the context of link-based classification and influence maximization.

REFERENCES

• 1: A.-L. Barabasi and E. Bonabeau. Scale-free networks. Scientific American, 288:50--59, May 2003.
• 2: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 3: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 4: Lise Getoor , Christopher P. Diehl, Link mining: a survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.3-12, December 2005 [doi>10.1145/1117454.1117456]
• 5: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 6: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 7: Q. Lu and L. Getoor. Link-based classification. In International Conference on Machine Learning, 2003.
• 8: M. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69, Feb 2004.
• 9: L. Page, S. Brin, R. Motwani, and T. Winograd. Pagerank citation ranking: Bringing order to the web. Technical report, Stanford University, 1998.
• 10: J. Scripps and P. N. Tan. Clustering in the presence of bridge-nodes. Proc of SDM'06: SIAM Int'l Conf on Data Mining, Bethesda, MD, 2006.
• 11: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 12: S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, UK, 1994.
• 13: D. J. Watts and S. H. Strogatz. Collective dynamics of Ssmall-worldS networks. Nature, pages 440--442, June 1998.
• 14: Yiming Yang , Seán Slattery , Rayid Ghani, A Study of Approaches to Hypertext Categorization, Journal of Intelligent Information Systems, v.18 n.2-3, p.219-241, March-May 2002 [doi>10.1023/A:1013685612819]