The most successful application of graph mining is web search, where the Internet is modeled as a network, and webpages are nodes. Each webpage is ranked based on their link strength.
Other applications of graph mining include:
1. Understand molecule structure for drug discovery 
2. Predict the spread of infectious diseases.
Any social network can be modeled as a graph, where nodes are people and edges are their relationship. On Facebook, the edges are "friend". On Twitter, the edges become “followed by”. On LinkedIn, the edges are “connection”. On eBay, the edges can be “sold to”.
How do we make use of the network structure? For marketers, finding out top influencers in a social network can be very useful. These people would influence a lot of people with their opinions. Marketing can be much more effective by focusing on these influencers.
How do we discover influencers? In Facebook, these are people who have a lot of friends and whose postings get a lot of comments. In Twitter, these people have many followers and whose tweets are retweeted often. Note that it is possible for a top influencer to have a small number of friends (or followers), as long as these friends (or followers) are top influencers. Such a person could be a “king maker”, who directly influences the most powerful/influential politician.
Mining top influencers therefore involves an algorithm like PageRank, which is successfully used to discover top web pages. The essence of PageRank algorithm is recursive calculation of the weights on each link. This can be applied to calculating top influencers, where their influence strength can be recursively based on their followers' influence level.
Given 100 million people in a network, mining top influencers is a computational challenge. Fortunately such computing can be parallelized as each node can by calculated simultaneously. This is how Google invented MapReduce, and how Hadoop came to be. Essentially, the so-called “Big Data” is about providing parallel computing infrastructure (such as Hadoop). Graph mining pioneered big data computing.
 Takigawa, Ichigaku, and Hiroshi Mamitsuka. "Graph mining: procedure, application to drug discovery and recent advances." Drug Discovery Today, Volume 18, Issues 1–2, January 2013, Pages 50–57