臺灣博碩士論文加值系統

在行動通訊的環境中，通聯記錄的產生是由行動使用者進行發話或受話時所自動產生，當我們更進ㄧ步探討通聯記錄的內容時，發現其不只是記錄使用者之間的收發話行為，更隱含了行動使用者之間的人際關係，更明確地來說，我們可以試圖由通聯記錄中找出熟識的行動使用者社群，這樣的社群關係包含家人、鄰居、同事、以及同學等，而對於電信業者來說，從通聯記錄了解行動使用者社群之行為模式深具實務上的重要性。因此，在本論文中我們善用了通聯記錄中所記載之時空關係，將其轉換成圖形化之人際網路來加以探討，更提出一演算法PECT來找出行動使用者社群。最後，由實驗結果中可驗證我們所提出之方法不僅具理論完整性，並且可以應用於真實的資料環境。

In a telecommunication system, call detail records (i.e., CDRs) are generated automatically for tracking and billing purposes when mobile users having calls. To further investigate the information buried in huge amounts of CDRs, relationship among mobile users can be organized. Specifically, communities of acquainted mobile users can be effectively discovered from collected CDRs through our approach proposed in this thesis. Examples of such communities include cohabiting family members, familiar neighborhood, colleagues and schoolmates. Note that understanding the communities and corresponding calling behaviors are of great importance to telecommunication companies. In addition, both spatial and temporal connections for such communities are exploited to conduct proper community mining on CDRs. Consequently, we derive an algorithm PECT (which stands for Partitioning by Expanding Conjunctive Triangles) by integrating techniques of data transformation and social network analysis. Our study shows that the proposed approach is not only theoretically effective but also practically feasible.

Chapter 1 Introduction 1
1.1 Motivation and Overview of the Thesis 1
1.2 Contributions of the Thesis 2
Chapter 2 Literature Survey 4
2.1 Data Management of Telecommunication Applications 4
2.1.1 Data Colleted in the Telecommunication Environment 4
2.1.2 Usage of Call Detail Records 5
2.2 Graphical Presentations and Corresponding Applications 7
2.3 Data Clustering Techniques 10
2.4 Community Mining and Graph Partitioning 12
2.4.1 Community Mining 12
2.4.2 Graph Partitioning 13
2.4.3 Overlapping Community 16
Chapter 3 Mining Mobile Communities on Call Detail Records 18
3.1 Overview of Mining Mobile Communities 18
3.1.1 Identifying Mobile Communities 19
3.1.2 Formal Definition of Communities in a Connected Graph 19
3.2 Data Preprocessing Steps 21
3.2.1 Transforming Call Detail Records to Graphs 21
3.2.2 Limitations of Existing Graph Partitioning Techniques 23
3.3 Proposed Approach for Mining Mobile Communities 24
3.3.1 Algorithm PECT 24
3.3.2 Extensive Discussions of Algorithm PECT 26
3.4 Implementation of Proposed Approach 27
3.4.1 Classical Process for Knowledge Discovery 27
3.4.2 Data Preprocessing 28
3.4.3 Code Design Flow of Algorithm PECT 32
Chapter 4 Empirical Studies 34
4.1 Testing Environment 34
4.2 Results of Data Preprocessing 34
4.3 Results of Utilizing Algorithm PECT 35
Chapter 5 Conclusions and Future Works 43
Bibliography 45

[1]N. Alon, “Spectral Techniques in Graph Algorithms,” In Lecture Notes in Computer Science, pages 206-215, April 1998.
[2]B. Adamcsek, G. Palla, I. J. Farkas, I. Derenyi and T. Vicsek, “CFinder: Locating Cliques and Overlapping Modules in Biological Networks,” Bioinformatics, 22(8):1021-1023, January 2006.
[3]M. Ankerst, M. M Breuning, H. -P. Kriegel and J. Sander, “OPTICS: Ordering Points to Identify the Clustering Structure,” In Proceedings of the 1999 ACM SIGMOD international Conference on Management of Data, pages 49-60, May 31 - June 03, 1999.
[4]C. Borgelt and M. R. Berhold, “Mining Molecular Fragments: Finding Relevant Substructures of Molecules,” Proceedings of International Conference on Data Mining, pages 51-58, December 2002.
[5]C. Borgs, J. T. Chayes, M. Mahdian and A. Saberi, “Exploring the Community Structure of Newsgroups,” Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 783-787, August 2004.
[6]U. Brandes, M. Gaertler and D. Wagner, “Experiments on Graph Clustering Algorithm,” In European Symposium on Algorithm, pages 568-579, September 2003.
[7]A. Ben-Hur and I. Guyon, “Detecting Stable Clusters Using Principal Component Analysis,” In Methods in Molecular Biology, pages 159-182, 2003.
[8]J. Baumes, M. K. Goldberg, M. S. Krishnamoorthy, M. Magdon-Ismail and N. Preston, “Finding Communities by Clustering a Graph into Overlapping Subgraphs,” Proceedings of the IADIS International Conference on Applied Computing, pages 97-104, February 2005.
[9]J. Baumes, M. Goldberg and M. Magdon-Ismail, “Efficient Identification of Overlapping Communities,” IEEE International Conference on Intelligence and Security Informatics, pages 27-36, May 2005.
[10]D. Cai, Z. Shao, X. He, X. Yan, and J. Han, “Community Mining from Multi-relational Networks,” Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, pages 445-452, October 2005.
[11]I. S. Dhillon, S. Mallela, D. S. Modha. “Information Theoretic Co-clustering.” ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 89-98, August 24-27 2003.
[12]P. Domingos and M. Richardson, “Mining the Network Value of Customers,” ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 57-66, August 2001.
[13]P. Drineas, A. Kannan, R. Vempala and V. Vinay, “Clustering in Large Graphs and Matrices, ” In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithm, pages 291-299, January 1999.
[14]S. V. Dongen, “Graph Clustering by Flow Simulation,” PhD thesis, University of Utrecht, 2000.
[15]I. Derenyi, G. Palla and T. Vicsek, “Clique Percolation in Random Networks,” Physical Review Letters, 94, 160202, 2005.
[16]J. Eckmann and E. Moses, “Curvature of Co-links Uncovers Hidden Thematic Layers in the World Wide Web,” Proceedings of the National Academy of Sciences, 99(9):5825-5829, April 2002.
[17]B. S. Everitt, “Cluster Analysis,” John Wiley, New York, 1974.
[18]G. W. Flake, S. Lawrence and C. L. Giles, “Efficient Identification of Web Community,” In Conference of the ACM Special Interest Group on Knowledge Discovery and Data Mining, pages 150-160, August 2000.
[19]M. Girvan and M. E. J. Newman, “Community Structure in Social and Biological Networks,” In proceedings of the National Academy of Sciences, 99(12):7821-7826, June 2002.
[20]D. Gibson, J. Kleinberg and P. Ragavan, “Inferring Web Communities from Link Topology,” In ACM Conference on Hypertext and Hypermedia, pages 225-234, 1998.
[21]S. Guha, R. Rastogi and K. Shim, “CURE: An Efficient Clustering Algorithm for Large Databases,” Proceedings ACM SIGMOD International Conference on Management of Data, pages 73-84, June 1998.
[22]C.-C. Hung, W.-C. Peng, and J.-L. Huang, “Exploring Regression for Mining User Moving Patterns in a Mobile Computing System,” Proceedings of the 1st International Conference on High Performance Computing and Communications, pages 878-887, September 2005.
[23]J. Huan, W. Wang, A. Washington, J. Prins, and A. Tropsha, “Accurately Classification of Protein Structural Families Using Coherent Subgraph Analysis,” Proceedings of Pacific Symposium on Biocomputing, pages 411-422, January 2004.
[24]J. Han and M. Kamber, “Data Mining: Concepts and Techniques,” Morgan Kaufmann Publishers, 2001.
[25]A. Inokuchi, T. Washio, K. Nishimura and H. Motoda, “A Fast Algorithm for Mining Frequent Connected Subgraphs,” Technical Report RT0448, IBM Research, Tokyo Research. Laboratory, 2001.
[26]R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, “Trawling the Web for Emerging Cyber Communities,” Proceedings of the 8th International World Wide Web Conference, 1999.
[27]M. Kuramochi and G. Karypis, “An Efficient Algorithm for Discovering Frequent Subgraphs,” IEEE Transactions on Knowledge and Data Engineering, 16(9):1038-1051, January 2001.
[28]R. Kannan, S. Vempala, and A. Vetta, “On Clustering: Good, Bad and Spectral,” Journal of the ACM, 51(3):497-575, May 2004.
[29]G. Karypis and V. Kumar, “Multilevel Algorithms for Multi-constraint Graph Partitioning,” Proceeding of 6th International Euro-Par Conference, pages 296-310, August 1998.
[30]J. Kleinberg, “Authoritative Sources in a Hyperlinked Environment,” Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 668-677, January 1998.
[31]L.Kaufman and P. J. Rousseeuw, “Finding Groups in Data: An Introduction to Cluster Analysis,” John Wiley, 1990.
[32]X. Li, B. Liu and P. S. Yu. “Mining Community Structure of Named Entities from Web Pages and Blogs,” Proceedings of the AAAI Spring 2006 Symposia on Computational Approaches to Analysing Weblogs, March 2006.
[33]M. Mukherjee, and L. B. Holder. “Graph-based Data Mining on Social Networks,” Workshop on Link Analysis and Group Detection (in conjunction with KDD), 2004.
[34]J. Moody, “Race, School Integration, and Friendship Segregation in America,” American Journal of Sociology, 107:679-716, 2001.
[35]R. T. Ng and J. Han, “Efficient and Effective Clustering Methods for Spatial Data Mining,” Proceedings of the 20th International Conference on Very Large Data Bases, pages 144-155, September 1994.
[36]L. Page, S. Brin, R. Motwani and T. Winograd, “The PageRank Citation Ranking: Bringing Order to the Web,” Stanford Digital Libraries Working Paper, 1998.
[37]J. Scott, “Social Network Analysis: a Handbook,” Sage Publications, 2002.
[38]J. Sun, H. Qu, D. Chakrabarti and C. Faloutsos, “Relevance Search and Anomaly Detection in Bipartite Graphs,” SIGKDD Explorations, 7(2):48-55, June 2005.
[39]M. F. Schwartz, and D. C. M. Wood, “Discovering Shared Interests Using Graph Analysis,” Communication of the ACM, 36(8):78-89, August 1993.
[40]J. R. Tyler, D. M. Wilkinson and B. A. Huberman, “Email as Spectroscopy: Automated Discovery of Community Structure within Organizations,” Proceeding of 1st International Conference Communities and Technologies, pages 81-96, September 2003.
[41]R. Tibshirani, G. Walther and T. Hastie, “Estimating the Number of Clusters in a Dataset via the Gap Statistic,” Journal of the Royal Statistical Society, 63(2):411-423, 2001.
[42]G. M. Weiss, “Data Mining in Telecommunications,” The Data Mining and Knowledge Discovery Handbook, pages 1189-1201, 2005.
[43]S. Wasserman, and K. Faust, “Social Network Analysis,” Cambridge University Press, 1994.
[44]C. Wang, W. Wang, J. Pei, Y. Zhu and B. Shi, “Scalable Mining of Large Disk-based Graph Database,” Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 316-325, August 2004.
[45]D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature 393: 440-442, 1998.
[46]F. Wu and B. A. Huberman, “Finding Communities in Linear Time: A Physics Approach,” The European Physical Journal B-Condensed Mater, 38(2):331-338, March 2004.
[47]L. Yan, M. Fassino, and P. Baldasare, “Predicting Customer Behavior via Calling Links,” International Joint Conference on Neural Networks, July 2005.
[48]X. Yan and J. Han, “gSpan: Graph-based Substructure Pattern Mining,” Proceedings of the 2002 IEEE International Conference on Data Mining, pages 721-724, December 2002.
[49]W.-J. Zhou, J.-R. Wen, W.-Y. Ma, and H.-J. Zhang, “A Concentric-circle Model for Community Mining,” Technical report, Microsoft Research, 2002.
[50]T. Zhang, R. Ramakrishnan and M. Livny, “BIRCH: An Efficient Data Clustering Method for Very Large Databases,” Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 103-114, June 1993.