Abstract:

Graph structures provide a general framework for modeling entities and their relationships, and they are routinely used to describe a wide variety of data such as the Internet, the web, social networks, metabolic networks, protein-interaction networks, food webs, citation networks, and many more. In the recent years there has been an increasing amount of literature on studying properties, models, and algorithms for graph data. In this chapter we give a brief overview of graph-mining algorithms, focusing on web and social-media applications. The set of topics we review ranges from algorithms for estimating reputation and popularity of items in a network, to algorithms for mining query logs and performing query recommendations. The main goal of the chapter is to present the reader with a number of applications where exploiting the graph structure is beneficial for certain data-mining tasks and to highlight challenges of graph mining in the context of problems appearing in web and social-media applications.