Abstract: Considering at the concept drift issue of machine learning identification, a novel algorithm called traffic classification based on Host Connection Graph (HCG) is proposed. Considering {IP Address, Port} as the unique user identifier, HCG constructs a host connection graph and innovates the concept of user similarity. Based on the theory of graph mining, social community is abstracted from communications among hosts by partitioning the graph into mutually intersectant behavior clusters. In order to reach traffic classification, HCG not only conceives a definition called User Behavior Mode (UBM) to analyse the implicit traffic characteristics, but also maps application labels to every host behavior by employing UBM and Port. Finally, simulations are conducted based on the real network trace. Results demonstrate that HCG can circumvent the concept shift problem and ameliorate gracefully computational complication without sacrificing accuracy.