請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44371
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林守德(Shou-De Lin) | |
dc.contributor.author | Cheng-Te Li | en |
dc.contributor.author | 李政德 | zh_TW |
dc.date.accessioned | 2021-06-15T02:53:44Z | - |
dc.date.available | 2010-01-01 | |
dc.date.copyright | 2009-08-04 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-08-03 | |
dc.identifier.citation | [1] P. Appan, H. Sundaram and B. L. Tseng. Summarization and Visualization of Communication Patterns in a Large-Scale Social Network. In Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’06), 371-379, 2006.
[2] P. Bonacich. Factoring and Weighting Approach to Status Scores and Clique Identification. Journal of Mathematical Sociology, 2(2), 113-120, 1972. [3] R. Breiger, S. Boorman, and P. Arabie. An Algorithm for Clustering Relational Data with Application to Social Network Analysis and Comparsion with Multidimensional Scaling. Journal of Mathematical Psychology, 12: 328-383, 1975. [4] D. Cai, Z. Shao, X. He, X. Yan and J. Han. Mining Hidden Community in Heterogeneous Social Networks. In Proceedings of ACM SIGKDD Workshop on Link Discovery: Issues, Approaches and Applications (LinkKDD’05), 58-65, 2005. [5] D. Chakrabarti and C. Faloutsos. Graph Mining: Laws, Generators, and Algorithms. ACM Computing Survey, 38(1), 2006. [6] J. Chen, O. R. Zaiane, and R. Goebel. Detecting Communities in Social Networks Using Max-Min Modularity. In Proceedings of SIAM International Conference on Data Mining (SDM’09), 978-989, 2009. [7] N. Du, B. Wu, and B. Wang. Backbone Discovery in Social Networks. In Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence (WI’07), 100-103, 2007. [8] M. Field. Algebraic Connectivity of Graphs. Journal of Czechoslovak Math, 23:298-305, 1973. [9] L. C. Freeman. Centrality in Social Networks: Conceptual Clarification. Social Networks, 1(3), 215-319, 1979. [10] L. C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry, 40(6), 35-41, 1977. [11] M. S. Granovetter. The Strength of Weak Ties. American Journal of Sociology, 78(6), 1973. [12] R. Guimera and L. A. N. Amaral. Functional cartography of complex metabolic networks. Nature 433, 895-900, 2005. [13] S. Hettich and S. D. Bay. The UCI KDD Archive. http://kdd.ics.uci.edu, University of California, Irvine, Department of Information and Computer Science, 1999. [14] W. Hwang, T. Kim, M. Ramanathan, and A. Zhang. Bridging Centrality: Graph Mining from Element Level to Group Level. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’08), 336-344, 2008. [15] B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49:291-307, 1970. [16] J. Kleinberg. Authoritative Sources in Hyperlinked Environment. Journal of ACM, 46(5), 604-632, 1999. [17] V. Latora and M. Marchiori. A Measure of Centrality Based on the Network Efficiency. New Journal of Physics, 9(6):188, 2007. [18] S. D. Lin and H Chalupsky. Discovering and Explaining Nodes in Semantic Graph. IEEE Transactions on Knowledge and Data Engineering, 20(8), 1039–1052, 2008. [19] Y. R. Lin, J. Sun, P. Castro, R. Konuru, H. Sundaram, and A. Kelliher. MetaFac: Community Discovery via Relational Hypergraph Factorization. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09), 527-535, 2009. [20] B. Long, Z. M. Zhang, X. Wu, and P. S. Yu. Spectral Clustering for Multi-type Relational Data. In Proceedings of International Conference on Machine Learning (ICML’06), 585-592, 2006. [21] S. Navlakha, R. Rastogi and N. Shrivastava. Graph Summarization with Bounded Error. In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD’08), 419-432, 2008. [22] M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review, 45:167-256, 2003. [23] M. E. J. Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. Physics Review, E 69, 2004. [24] M. E. J. Newman. Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physics Review, E 74, 2006. [25] L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. In Technical Report, Stanford University, 1998. [26] V. Satuluri and S. Parthasarathy. Scalable Graph Clustering Using Stochastic Flows: Application to Community Detection. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09), 737-745, 2009. [27] R. Schrag. A Performance Evaluation Laboratory for Automated Threat Detection Technologies. In Proceedings of Performance Measures of Intelligent System Workshop (PerMIS’06), 2006. [28] J. Scripps, P. N. Tan, and A. H. Esfahanian. Exploration of Link Structure and Community-Based Node Roles in Network Analysis. In Proceedings of IEEE International Conference on Data Mining (ICDM’07), 649-654, 2007. [29] Z. Shen, K. L. Ma and T. Eliassi-Rad. Visual Analysis of Large Heterogeneous Social Networks by Semantic and Structural Abstraction. IEEE Transactions on Visualization and Computer Graphics, 12(6), 1427-1439, 2006. [30] J. Shetty and J. Adibi. Discovering Important Nodes through Graph Entropy: The Case of Enron Email Database. In Proceedings of ACM Workshop on Link Discovery (LinkKDD’05), 74-81, 2004. [31] L. Singh, M. Beard, L. Getoor and M. B. Blake. Visual Mining of Multi-Modal Social Networks at Different Abstraction Levels. In Proceedings of International Conference on Information Visualization (IV’07), 672-679, 2007. [32] J. Sun, D. Tao, and C. Faloutsos, Beyond Streams and Graphs: Dynamic Tensor Analysis. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’06), 374-383, 2006. [33] Y. Sun, Y. Yu, and J. Han. Ranking-Based Clustering of Heterogeneous Information Networks with Star Network Schema, In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09), 797-806, 2009. [34] L. Tang, H. Liu, J. Zhang, and Z. Nazeri. Community Evolution in Dynamic Multi-Mode Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’08), 677-685, 2008. [35] Y. Tian, R. A. Hankins and J. M. Patel. Efficient Aggregation for Graph Summarization. In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD’08), 567-580, 2008. [36] D. Vincent and B. Cecile. Transitive Reduction for Social Network Analysis and Visualization. In Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence (WI’05), 128-131, 2005. [37] S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, UK, 1994. [38] D. J. Watts and S. H. Strogatz. Collective Dynamics of Small-world Networks. Nature 393, 440-442, 1998. [39] H. C. White, S. Boorman, and R. Breiger. Social Structure from Multiple Networks. I. Blockmodels of Roles and Positions. American Journal of Sociology, 81: 730-780, 1976. [40] A. Y. Wu, M. Garland, and J. Han. Mining Scale-free Networks Using Geodesic Clustering. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’04), 719-724, 2004. [41] X. Xu, N. Yuruk, Z. Feng and T. A. J. Schweiger. SCAN: A Structural Clustering Algorithm for Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’07), 824-833, 2007. [42] J. Zhang, J. Tang, B. Liang, Z. Yang, S. Wang, J. Zuo and J. Li. Recommendation over a Heterogeneous Social Network. In Proceedings of International Conference on Web-Age Information Management (WIAM’08), 309-316, 2008. [43] D. Zhou, S. A. Orshanskiy, H. Zha, and C. L. Giles. Co-Ranking Authors and Documents in a Heterogeneous Network. In Proceedings of IEEE International Conference on Data Mining (ICDM’07), 739-744, 2007. [44] L. Zou, L. Chen, H. Zhang, Y. Li and Q. Lou. Summarization Graph Indexing: Beyond Frequent Structure-Based Approach. In Proceedings of International Conference on Database Systems for Advanced Applications (DASFAA’08), 141-155, 2008. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44371 | - |
dc.description.abstract | 社群網路是一種能夠描述個體彼此關係之資料結構,至目前相關研究人員在具有單一個體類型與單一關係類型之同質性網路,已成功提出許多網路分析之方法。然而,真實世界之複雜網路通常為異質性,亦即存在多重類型之個體與關係。本論文整合高階關係類型資訊,提出一種非監督式、以tensor為基礎之方法與模型,來捕捉異質性網路中節點之語意於一種signature profile之特徵空間。基於該模型,本論文解決三個異質性網路探勘之議題。首先,我們提出貢獻度、多樣性程度與相似度之三種異質性中心度指標,來衡量節點之重要性;接著,我們考慮節點於網路中扮演之角色來進行分群;最後,為簡化社群網路探查與視覺化之複雜度,我們萃取關於使用者指定節點之三種最具代表性的資訊,來進行以個體為中心之網路摘要。本論文使用一真實之電影網路與一合成之犯罪網路來進行實驗評估,對於異質性中心度量測與網路角色分群,我們展示探勘之結果及其物理意義,對於以個體為中心之資訊摘要,我們用於人為主觀之罪犯偵測,實驗結果顯示我們的方法能提供高準確、高效率、高信心水準之罪犯偵測。 | zh_TW |
dc.description.abstract | Social network is a powerful data structure allowing the depiction of relationship information between entities. Recent researchers have proposed many successful methods on analyzing homogeneous social networks, assuming only a single type of node and relation. Nevertheless, real-world complex networks are usually heterogeneous, which presumes a network can be composed of different types of nodes and relations.
In this thesis, we propose an unsupervised tensor-based mechanism, considering higher-order relational information, to model the complex semantics of nodes. The signature profiles are derived as a vector-based representation to enable further mining algorithms. Moreover, based on this model, we present solutions to tackle three critical issues in heterogeneous networks. First, we identify different aspects of central individuals through three proposed measures, including contribution-based, diversity-based, and similarity-based centrality. Second, we propose a role-based clustering method to identify nodes playing similar roles in the network. Third, to facilitate further explorations and visualization in a complex network data, we devise the egocentric information abstraction and address it by proposing three abstraction criteria to distill representative and significant information with respect to any given node. In the end, the evaluations are conducted on a real-world movie dataset, and an artificial crime dataset. We demonstrate the proposed centralities and role-based clustering can indeed find some meaningful results. And the effectiveness of the egocentric abstraction is shown by providing more accurate, efficient, and confidential crime detection for human subjects. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T02:53:44Z (GMT). No. of bitstreams: 1 ntu-98-R96944015-1.pdf: 1722580 bytes, checksum: 5c4e96194cbc96537b07395468d5f873 (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | Acknowledgements............i
Abstract............ii 摘要............iv Table of Contents............vi List of Figures............viii List of Tables............x Chapter 1 Introduction............1 1.1 Background............1 1.2 Heterogeneous Social Networks............1 1.3 Motivations............3 1.4 Research Objectives............6 1.5 The Proposed Solution............8 1.6 Thesis Organization............8 Chapter 2 Related Works............10 2.1 Node Centrality............10 2.2 Network Clustering............12 2.2.1 Community in Homogeneous Networks............13 2.2.2 Community in Heterogeneous Networks............13 2.2.3 Social Positions............14 2.3 Graph Abstraction and Summarization............15 Chapter 3 Modeling Heterogeneous Networks............18 3.1 Problem Definition............19 3.2 Relational Adjacency Matrix............19 3.3 Relational Adjacency Tensor............23 3.4 Signature Profiles............24 Chapter 4 Centrality and Role-based Clustering............28 4.1 Heterogeneous Centralities............28 4.1.1 Contribution-based Centrality............28 4.1.2 Diversity-based Centrality............30 4.1.3 Similarity-based Centrality............30 4.2 Role-based Entity Clustering............32 Chapter 5 Egocentric Information Asbtraction............34 5.1 Problem Definition............34 5.2 Feature Extraction............35 5.3 Dependency Computation............36 5.4 Information Distilling............38 5.4.1 Local Frequency............39 5.4.2 Local Rarity............39 5.4.3 Relative Frequency............40 5.5 Abstracted Graph Construction............40 Chapter 6 Evaluations............44 6.1 Experiment Design............44 6.2 Data Collections............45 6.3 Results of Heterogeneous Centralities............48 6.4 Results of Role-based Clustering............50 6.5 Egocentric Abstraction on Movie Dataset............55 6.6 Human Study for Crime Identification............57 6.7 Discussions............62 Chapter 7 Conclusions............64 7.1 Summary of Contributions............64 7.2 Future Works............65 Bibliography............67 | |
dc.language.iso | en | |
dc.title | 異質性社群網路探勘:中心度、分群、資訊摘要 | zh_TW |
dc.title | Mining Heterogeneous Social Networks: Centrality, Clustering, and Abstraction | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳銘憲(Ming-Syan Chen),吳家麟(Ja-Ling Wu),劉昭麟(Chao-Lin Liu) | |
dc.subject.keyword | 社群網路,中心度,分群,資訊摘要,異質性網路, | zh_TW |
dc.subject.keyword | Social Network,Centrality,Clustering,Information Abstraction,Heterogeneous Network, | en |
dc.relation.page | 71 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2009-08-04 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 1.68 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。