請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/18406完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 林守德(Shou-De Lin) | |
| dc.contributor.author | Yen-Kai Wang | en |
| dc.contributor.author | 王彥凱 | zh_TW |
| dc.date.accessioned | 2021-06-08T01:03:38Z | - |
| dc.date.copyright | 2014-09-05 | |
| dc.date.issued | 2014 | |
| dc.date.submitted | 2014-08-27 | |
| dc.identifier.citation | [1] Akoglu, Leman, Mary McGlohon, and Christos Faloutsos. 'Oddball: Spotting anomalies in weighted graphs.' Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 2010. 410-421.
[2] Chen, Wei, Chi Wang, and Yajun Wang. 'Scalable influence maximization for prevalent viral marketing in large-scale social networks.' Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010. [3] Chen, Wei, Yifei Yuan, and Li Zhang. 'Scalable influence maximization in social networks under the linear threshold model.' Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010. [4] Cook, Stephen A. 'The complexity of theorem-proving procedures.' Proceedings of the third annual ACM symposium on Theory of computing. ACM, 1971. [5] Cordella, Luigi P., et al. 'A (sub) graph isomorphism algorithm for matching large graphs.' Pattern Analysis and Machine Intelligence, IEEE Transactions on 26.10 (2004): 1367-1372. [6] Dhifli, Wajdi, RabieSaidi, and EngelbertMephuNguifo. 'Mining Representative Unsubstituted Graph Patterns Using Prior Similarity Matrix.' arXiv preprint arXiv:1303.2054 (2013). [7] G. Zhu, K. Zhu, W. Zhang, X. Lin and C. Xiao. Efficient Subgraph Similarity All-Mapping.DASFAA, 455-469, 2012. [8] Hassanzadeh, Reza, RichiNayak, and Douglas Stebila. 'Analyzing the effectiveness of graph metrics for anomaly detection in online social networks.' Web Information Systems Engineering-WISE 2012. Springer Berlin Heidelberg, 2012. 624-630. [9] Heard, Nicholas A., et al. ”Bayesian anomaly detection methods for social networks.” The Annals of Applied Statistics 4.2 (2010): 645-662. [10] Heggernes, Pinar, Pimvan’t Hof, and Martin Milanič. 'Induced Subtrees in Interval Graphs.' Combinatorial Algorithms. Springer Berlin Heidelberg, 2013. 230-243. [11] H. Tong,C.Faloutsos, B. Gallagher,andT. Eliassi-Rad. Fast best-effort pattern mapping in large attributed graphs. ACM SIGKDD, 737-746, 2007. [12] Jiang, Chuntao, FransCoenen, and Michele Zito. 'A survey of frequent subgraph mining algorithms.' The Knowledge Engineering Review 1.1 (2013): 1-31. [13] M. Thoma, H. Cheng, A.Gretton, J. Han, H.Kriegel, A.Smola, L. Song, P. S. Yu, X. Yan, and K. M. Borgwardt. Discriminative frequent subgraph mining with optimality guarantees. Statistical Analysis and Data Mining, 3(5), 302-318, 2010. [14] N. Jin and W. Wang. LTS: Discriminative subgraph mining by learning from search history. IEEE ICDE, 207-218, 2011. [15] Nijssen, Siegfried, and Joost N. Kok. 'Efficient discovery of frequent unordered trees.' First international workshop on mining graphs, trees and sequences. Vol. 2003. 2003. [16] Law, John. 'Notes on the theory of the actor-network: Ordering, strategy, and heterogeneity.' Systems practice 5.4 (1992): 379-393. [17] L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography. In WWW 2007. [18] Scott, John. 'Social network analysis.' Sociology 22.1 (1988): 109-127. [19] Shamir, Ron, and DekelTsur. 'Faster subtree isomorphism.' Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on. IEEE, 1997. [20] Shamir, Ron, and DekelTsur. 'Faster subtree isomorphism.' Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on. IEEE, 1997. [21] Thoma, Marisa, et al. 'Discriminative frequent subgraph mining with optimality guarantees.' Statistical Analysis and Data Mining 3.5 (2010): 302-318. [22] T. Lappas, K. Liu, and E. Terzi. Finding a Team of Experts in Social Networks. In ACM KDD 2009. [23] Y. Jeffrey Xu, D. Bolin, Y. Phillip S and W.Haixum. Fast Graph Pattern Mapping. IEEE ICDE, 913-922, 2008. [24] Y.Tian and J. M. Patel. TALE: A Tool for Approximate Large Graph Mapping. IEEE ICDE, 963-972, 2008. [25] Y.Tian, R. C. McEachin, C. Santos, D. J. States and J. M. Patel. SAGA: a subgraph mapping tool for biological graphs. Bioinformatics, 23(2), 232 [26] Zhang, Shijie, Jiong Yang, and Shirong Li. 'Ring: An integrated method for frequent representative subgraph mining.' Data Mining, 2009. ICDM'09. Ninth IEEE International Conference on. IEEE, 2009. [27] Zhou, Bin, Jian Pei, and WoShunLuk. 'A brief survey on anonymization techniques for privacy preserving publishing of social network data.' ACM SIGKDD Explorations Newsletter 10.2 (2008): 12-22. [28] Zhou, Bin, and Jian Pei. 'Preserving privacy in social networks against neighborhood attacks.' Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on. IEEE, 2008. [29] Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Efficient subgraph mapping on billion node graphs. VLDB Endow, 5(9), 788-799, 2012. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/18406 | - |
| dc.description.abstract | 本研究旨在尋找一個網路中的對於任一單元周邊發現有價值的網路結構。對於價值我們給予一個新的定義─簡單但獨特。而為了有效尋找這種結構我們將它化為一個子圖找尋問題。接著我們先檢驗這個問題所需要的複雜度不適合實際應用。再提出一個貪婪的作法在可行的時間內盡可能尋找最好的結構。最後我們將它應用在一個實際的社群網路上以驗證這個方法的實用性和有效性。 | zh_TW |
| dc.description.abstract | This paper proposes to study a novel problem, discovering a Smallest Unique Subgraph (SUS) for any node of interest specified by user in a heterogeneous social network. The rationale of the SUS problem lies in how a person is different from any others in a social network, and how to represent the identity of a person using her surrounding relational structure in a social network. To deal with the proposed SUS problem, we develop an Ego-Graph Heuristic (EGH) method to efficiently solve the SUS problem in an approximated manner. EGH intelligently examine whether one graph is not isomorphic to the other, instead of using the conventional subgraph isomorphism test. We also prove SUS is a NP-complete problem through doing a reduction from Minimum Vertex Cover (MVC) in a homogeneous tree structure. Experimental results conducted on a real-world movie heterogeneous social network data show both the promising efficiency and compactness of our method. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-08T01:03:38Z (GMT). No. of bitstreams: 1 ntu-103-R01922023-1.pdf: 2131217 bytes, checksum: 104eef03482db6f66157e877f7098ed6 (MD5) Previous issue date: 2014 | en |
| dc.description.tableofcontents | 摘要 ………………………………………………………………………… i
Abstract ………………………………………………………………………. i 目錄 ……………………………………………………………………………… ii List of Feagures ………………………………………………………………….. iii List of Tables ……………………………………………………………………. vi Chapter 1. Introduction…………………………………………………… 1 Chapter 2. Problem Statement and Analysis …………………………… 4 Chapter 3. Ego-Graph Heuristics Approach …………………………… 5 3-1. Algorithm Overview …………………………………………… 5 3-2. Extract k-layer Subgraph as Candidates …………………………. 6 3-3. Egocentric Information Table……………………………………… 6 3-4. Uniqueness Validation and Discovery……………………………… 9 3-5. Finding Unique Subgraphs………………………………………… 12 Chapter 4. Smallest Unique Subtree ……………………………………… 14 4-1. Problem Statement…………………………………………………… 15 4-2. Proof Sketch for the Reduction from MVC to SUS-T……………… 18 4-3. Problem Mapping ………………………………………………… 19 Chapter 5. Experiments ………………………………………………… 20 5-1. Dataset……………………………………………………………… 20 5-2. Evaluation Settings………………………………………………… 20 5-3. Experiment Results………………………………………………… 21 Chapter 6. Related Work ……………………………………………… 23 Chapter 7. Conclusion…………………………………………………… 23 參考文獻…………………………………………………………………….…… 25 附錄………………………………………………………………………………. 28 | |
| dc.language.iso | zh-TW | |
| dc.title | 在異質性社群網路中尋找最小獨特子圖 | zh_TW |
| dc.title | Identifying Smallest Unique Subgraphs in a Heterogeneous Social Network | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 102-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 李政德(Cheng-Te Li),趙坤茂(Kun-Mao Chao),呂育道(Yuh-Dauh Lyuu),葉彌妍(Mi-Yen Yeh) | |
| dc.subject.keyword | 獨特,最小,子圖,異質性,全等, | zh_TW |
| dc.subject.keyword | unique,smallest,subgaph,heterogeneous,isomorphism, | en |
| dc.relation.page | 40 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2014-08-28 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-103-1.pdf 目前未授權公開取用 | 2.08 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。