Internet traffic classification plays an important role in many aspects of network management such as exploit data detection, malicious user intention identification and applying traffic restriction on some applications. In the past, some features such as port numbers and protocol numbers were used to classify traffic, but nowadays ease of changing these features makes traffic classification inefficient. Consequently traffic classification based on machine learning methods is more common recently . In general, the machine learning based approached are categorized to the supervised learning with completely labeled training data, and the unsupervised learning without any labeled training data. Since, in the network traffic classification, obtaining the true label of instances is expensive, the supervised learning methods may not be practical. Therefore, semi-supervised learning methods should be applied to classify the encrypted traffic. In this thesis, a new semi-supervised classification method is presented that exploits clustering and the proposed labeling mechanism. The clustering step is performed using graph theory and the minimum spanning tree concepts. Next, some instances are selected to ask their true labels from expert system these labels are applied to label all the unlabeled instances. Finally, the decision tree algorithm is employed to build the classification model using the fully labeled dataset. Experimental results show that the proposed method has high precision in the identification and classification of the network applications based on the encrypted traffics. Moreover, this method for the unencryptedtraffic flow and unbalancedtraffic flow gives good results. Keywords Internet traffic classification, Encrypted traffic, Graph theory