Discovering the influencers in the new social network is very important for the promotion of products and the supervision of public opinion. Most of the previous research was based on the method of mining influential individuals, while the tribe-leaders were neglected. In this paper, a new method of mining tribe-leaders is proposed based on the frequent pattern of propagation. First, a method of changing the diffusion trees is proposed to overcome the problem of multi-pattern in propagation, where the information propagation trees are changed into a connected undirected acyclic graph. Then, a new frequent subgraph mining method called Tribe-FGM is proposed to improve the efficiency of graph mining by reducing the scale of pattern growth. Experiments are conducted on a real dataset, and the results show that Tribe-FGM is more effective than the method of Unot.