近年來，由於社群網站和應用程式的普及，大部分的研究都集中在結構化的社群網路分析中。現在許多的社會現象，在實際應用中，可以由社群網路中提取有意義的社交模式。然而，建立或刪除過時的用戶和關係，這通常隨著時間而演變，這樣的動態特性絕對會增加模式探勘的複雜度，過去一些研究已經提出在動態網絡的探索模式，這些研究通常將動態社群網絡處理成為一系列的關係圖，並從每個關係圖中探勘出有意義的子圖形（聚集），最後整合探勘結果成為一個序列，事實上，這些序列子圖或聚集可能不足以揭示個人的演化特徵; 以使用者的角度而言，隨著時間變化它仍然是難以觀察出與其他個體相互作用的演化。在本論文中，我們採用一個新的的表示法來表達動態社群網絡和一個新型的模式，以及演化特徵，並在一個動態社群網絡中獲取互動演化樣式。 此外，提出一個新的演算法Evolution Characteristic Miner (ECM),有效的提昇探勘效率與維護演化特徵。ECM還採用了一些優化策略，有效地減少搜尋空間以提高性能。使用虛擬與實際資料庫的實驗結果表示ECM於動態社群網路中探勘互動演化樣式的效率，並擁有優雅的可擴展性。最後，我們應用在真實數據集ECM顯示演變特徵挖掘的實用性。

Recently, due to the popularity of social website and APP, considerable attention has been paid to the analysis of structure in social network. Many potential social phenomena, in practice, can be extracted by discovering significant pattern in social network. Clearly, the network usually evolves with time; some new users and relationships are established, and some obsolete ones are removed. This dynamic feature definitely increases the complexity of pattern discovery. Several prior studies have proposed to discover pattern in dynamic network. These works generally treat the dynamic social network as a series of graphs and discover the significant subgraphs (clusters) from each graph, and then integrate the discovered results into a series. However, in fact, the series of subgraphs or clusters may be insufficient to reveal the evolving characteristics of individuals; in user’s point of view, it is still difficult to observe the evolution of interaction with other individuals over time. In this dissertation, we introduce a new representation to express the dynamic social network and a new type of pattern, evolution characteristic, to capture the interaction evolutions in a dynamic social network. Furthermore, a novel algorithm, Evolution Characteristic Miner (ECM), is developed to discover and maintain the evolution characteristics efficiently. ECM also employs some pruning strategies to effectively reduce the search space to improve the performance. The experimental results on synthetic and real datasets show the efficiency of ECM for extracting interaction evolution in dynamic networks, and possess graceful scalability. Finally, we apply ECM on real datasets to show the practicability of evolution characteristic mining.

Table of Contents

Chinese Abstract I
Abstract II
Table of Contents IV
List of Figures VI
Chapter 1  Introduction	1
Chapter 2  Related work	6
2.1 Pattern Mining in Dynamic Social Networks	6
2.2 Pattern Mining in Interval databases	8
Chapter 3  Problem Definition	10
3.1 Preliminary	10
Definition 1 (Dynamic Social Network)	10
Definition 2 (Interaction Interval and Evolution Sequence)	11
3.2 Interaction Expression and Evolution Characteristic	11
Definition 3 (Interaction Expression).	12
Definition 4 (Evolution Database)	13
Definition 5 (Evolution Characteristic)	14
Chapter 4  Algorithm: Evolution Characteristic Miner (ECM)	16
4.1 Evolution Characteristic Mining	16
4.2 Evolution Characteristic Maintenance	21
Definition 6 (Evolution Pattern Tree)	22
Definition 7 (Updated Network and Database)	23
Definition 8 (Search Space Reduction)	26
Chapter 5  Experiments	31
Chapter 6  Conclusions	35
Reference	36


 
List of Figures 

Fig. 1: An illustration of the significant subgraph evolution in a dynamic social network.	2
Fig. 2: Overview of the ECM Framework.	3
Fig. 3: An example of the dynamic social network and transformed evolution database.	13
Fig. 4: The evolution pattern tree of DB in Fig. 3 with min_sup = 2.	22
Fig. 5: Concept of network and database update	24
Fig. 6: An example of the updated network and database.	25
Fig. 7: The search space reduction on EPTDB of database DB in Fig. 6	28
Fig. 8: The runtime performance of two datasets	32
Fig. 9: The memory usage of two datasets	32
Fig. 10: The influence of proposed pruning strategies	33

[1] 	Allen, J. 1983. Maintaining Knowledge about Temporal Intervals. Communications of ACM 26(11) 832-843.
[2] 	Asur, S., Parthasarathy, S., and Ucar, D. 2007. An event-based framework for characterizing the evolutionary behavior of interaction graphs. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’07). 913-921.
[3] 	Berlingerio, M., Bonchi, F., Bringmann, B., and Gionis, A. 2009. Mining Graph Evolution Rules. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD’09). 115-130.
[4] 	Borgwardt, K., Kriegel, H., and Wackersreuther, P. 2006. Pattern mining in frequent dynamic subgraphs. In Proceedings of the 6th International Conference on Data Mining (ICDM’06). 818-822.
[5] 	Chakrabarti, D., Kumar, R., and Tomkins, A. 2006. Evolutionary clustering. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’06). 554-560.
[6] 	Chen, Y., Jiang, J., Peng, W., and Lee, S. 2010. An Efficient Algorithm for Mining Time Interval-based Patterns in Large Databases. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM’10). 49-58.
[7] 	Chi, Y., Song, X., Zhou, D., Hino, K., and Tseng, B. 2007. Evolutionary Spectral Clustering by Incorporating Temporal Smoothness. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’07). 153-162.
[8] 	Desikan, P. and Srivastava, J. 2004. Mining Temporally Evolving Graphs. In Proceedings of the 6th International Workshop on Knowledge Discovery from the Web (WEBKDD’04).
[9] 	Hopper, F. 2002. Finding informative rules in interval sequences. Intelligent Data Analysis 6(3). 237-255.
[10] 	Inokuchi, A., and Washio, T. 2008. A fast method to mine frequent subsequences from graph sequence data. In Proceeding of the 8th IEEE International Conference on Data Mining (ICDM’08). 303-312.
[11] 	Kam, P., and Fu, W. 2000. Discovering Temporal Patterns for Interval-based Events. In International Conference on Data Warehousing and Knowledge Discovery (DaWaK’00). 317-326.
[12] 	Kim, M., and Han, J. 2009. A Particle-and-Density based Evolutionary Clustering Method for Dynamic Networks. In Proceedings of the 35th International Conference on Very Large Data Bases (VLDB’09).
[13] 	Lahiri, M., and Berger-Wolf, T. 2007. Structure Prediction in Temporal Networks using Frequent Subgraphs. In Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Data Mining (CIDM’07). 35-42.
[14] 	Lin, Y., Chi, Y., Zhu, S., Sundaram, H., and Tseng, B. 2008. Facetnet: A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks. In Proceedings of the 17th International Conference on the World Wide Web (WWW’08). 685-694.
[15] 	Liu, Z., Yu, J., Ke, Y., Lin, X., and Chen, L. 2008. Spotting significant changing subgraphs in evolving graphs. In Proceeding of the 8th IEEE International Conference on Data Mining (ICDM 2008). 917-922.
[16] 	Morchen, F., and Ultsch, A. 2007. Efficient Mining of Understandable Patterns from Multivariate Interval Time Series. Data Mining Knowledge Discovery 15(2) 181-215.
[17] 	Morchen, F., and Fradkin, D. 2010. Robust mining of time intervals with semi-interval partial order patterns. In: Proceedings of the SIAM International Conference on Data Mining (SDM’10). 315-326.
[18] 	Palla, G., Barabási, A., and Vicsek, T. 2007. Quantifying social group evolution. Nature 446, 664-667.
[19] 	 Papapetrou, P., Kollios, G., Sclaroff, S., and Gunopulos, D. 2005. Disovering Frequent Arrangements of Temporal Intervals. In International Conference on Data Mining (ICDM’05). 354-361.
[20] 	Patel, D., Hsu, W., and Lee, M. 2008. Mining Relationships Among Interval-based Events for Classification. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, 393-404.
[21] 	Qin, G., Gao, L., Yang, J., and Li, J. 2011. Evolution Pattern Discovery in Dynamic Networks. In: IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC’11).
[22] 	Sadasivam, R., and Duraiswamy, K. 2013. Efficient Method to Discover Interval-based Sequential Patterns. Journal of Computer Science 9, 2, 225-234.
[23] 	Wackersreuther, B., Wackersreuther, P., Oswald, A., Bohm, C., and Borgwardt, K. 2010. Frequent Subgraph Discovery in Dynamic Networks. In: Proceedings of the 8th Workshop on Mining and Learning with Graphs (MLG’10), 155-162.
[24] 	Winarko, E., and Roddick, J. 2007. ARMADA-An algorithm for discovering richer relative temporal association rules from interval-based data. Data and Knowledge Engineering 63, 1. 76-90.
[25] 	Wu, S., and Chen, Y. 2007. Mining Nonambiguous Temporal Patterns for Interval-based Events. IEEE Transactions on Knowledge and Dta Engineering 19, 6, 742-758.
[26] 	Wu, S., and Chen, Y. 2009. Discovering hybrid temporal patterns from sequences consisting of point- and interval-based events. Data & Knowledge Engineering 68, 11, 1309-1330.
[27] 	You, C., Holder, L., Cook, D. 2009. Learning Patterns in the Dynamics of Biological Networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09).
[28] 	Zhang, L., Chen, G., Brijs, T., and Zhang, X. 2008. Discovering during-temporal patterns (DTPs) in large temporal databases. Expert Systems with Applications 34, 1178-1189.