請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/54122
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳銘憲(Ming-Syan Chen) | |
dc.contributor.author | Hong-Han Shuai | en |
dc.contributor.author | 帥宏翰 | zh_TW |
dc.date.accessioned | 2021-06-16T02:40:55Z | - |
dc.date.available | 2015-07-24 | |
dc.date.copyright | 2015-07-24 | |
dc.date.issued | 2015 | |
dc.date.submitted | 2015-07-22 | |
dc.identifier.citation | [1] N. K. Ahmed, J. Neville, and R. Kompella, “Network sampling: from static to streaming graphs,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 8, no. 7, 2013.
[2] S. Lee, P. J. Kim, and H. Jeong, “Statistical properties of sampled networks,” In Phys. Rev. E, vol. 73, 2006. [3] M. Gjoka, M. Sirivianis, A. Markopoulou, and X. Yang, “Poking facebook: characterization of osn applications,” In WOSN, pp. 31–36, 2008. [4] M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork, “On near-uniform url sampling,”In WWW, vol. 33, pp. 295–308, 2000. [5] M. Gjoka, M. Kurant, C. Butts, and A. Markopoulou, “Walking in facebook: a case study of unbiased sampling of osns,” In Infocom, pp. 1–9, 2010. [6] A. S. Maiya and T. Y. Berger-Wolf, “Benefits of bias: towards better characterization of network sampling,” In KDD, 2011. [7] M. D. Domenico, A. Sol-Ribalta, E. Cozzo, M. Kivel, Y. Moreno, M. A. Porter, S. Gmez, and A. Arenas, “Mathematical formulation of multilayer networks,” In Phys. Rev., vol. 3, 2013. [8] I. Bhattacharya and L. Getoor, “Collective entity resolution in relational data,” ACMTransactions on Knowledge Discovery from Data (TKDD), vol. 1, no. 5, 2007. [9] P. Jain, P. Kumaraguru, and A. Joshi, “@i seek ’fb.me’: identifying users across multiple online social networks,” In WWW, pp. 1259–1268, 2013. [10] X. Kong, J. Zhang, and P. Yu, “Inferring anchor links across heterogeneous social networks,” In CIKM, pp. 179–188, 2013. [11] R. Zafarani and H. Liu, “Connecting users across social media sites: a behavioralmodeling approach,” In KDD, pp. 41–49, 2013. [12] A. F. J. Tang, B. Wang, and J. Zhang, “A unified probabilistic framework for name disambiguation in digital library,” IEEE Transactions on Knowledge and Data Engineering (TKDE), vol. 24, pp. 975–987, 2012. [13] “Qmsampler package,” http://arbor.ee.ntu.edu.tw/∼hhshuai/QMSampler.gz. [14] Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, “Analysis of topological characteristics of huge online social networking services,” In WWW, pp. 835–844, 2007. [15] A. Mislove, M. Marcon, K. Gummadi, P. Druschel, and S. Bhattacharjee, “Measurement and analysis of online social networks,” In IMC, pp. 29–42, 2007. [16] D. Stutzbach, R. Rejaie, N. Duffield, S. Sen, andW.Willinger, “On unbiased sampling for unstructured peer-to-peer networks,” In IMC, pp. 377–390, 2006. [17] J. Leskovec and C. Faloutsos, “Sampling from large graphs,” In KDD, pp. 631–636, 2006. [18] O. Mathew, A. Sola, B. Oladiran, and A. Amos, “Efficiency of neyman allocation procedure over other allocation procedures in stratified random sampling,” In AJTAS, vol. 2, no. 5, pp. 122–127, 2013. [19] L. Lovasz, “Random walks on graphs: a survey,” In Combinatorics: Paul Erdos is 80, 1994. [20] A. Clauset, C. R. Shalizi, and M. E. J. Newman, “Power-law distributions in empirical data,” In SIAM Rev., vol. 51, no. 4, pp. 661–703, 2009. [21] C. Avin and G. Ercal, “On the cover time and mixing time of random geometric graphs,” Theor. Comput. Sci., vol. 380, pp. 2–22, 2007. [22] “The PPGG package,” http://lkto.co/9I6e. [23] T. Hagedorn, “General formulas for solvable sextic equations,” J. Algebra, vol. 233, pp. 704–757, 2000. [24] “Twitter statistics,” http://www.statisticbrain.com/twitter-statistics. [25] V. Pan, “Solving a polynomial equation: some history and recent progress,” In SIAM Review, pp. 187–220, 1997. [26] J. Leskovec and C. Faloutsos, “Scalable modeling of real graphs using kronecker multiplication,” In ICML, pp. 497–504, 2007. [27] “Stanford large network dataset collection,” http://snap.stanford.edu/data. [28] “Ucsb social network dataset collection,” http://current.cs.ucsb.edu/socialnets. [29] “Statistics from hashtags.org,” http://goo.gl/34Fwg1. [30] “Statistics from radicati group,” http://goo.gl/5t1m2Z. [31] H. Moe and A. O. Larsson, “Methodological and ethical challenges associated with largescale analyses of online political communication,” Nordicom Review, vol. 33, no. 1, pp. 117–124, 2012. [32] M. Durr, P. Marcus, and K. Wiesner, “Secure, privacy-preserving, and context-restricted information sharing for location-based social networks,” In Proc. ICWMC, pp. 243–248, 2011. [33] W. F. Fan, J. Z. Li, X. Wang, and Y. H. Wu, “Query preserving graph compression,” In Proc. SIGMOD, pp. 157–168, 2012. [34] U. Kang, C. E. Tsourakakis, and C. Faloutsos, “Pegasus: A peta-scale graph mining system - implementation and observations,” In Proc. of ICDM, 2009. [35] F. Zhu, Q. Qu, D. Lo, X. Yan, J. Han, and P. S. Yu., “Mining top-k large structural patterns in a massive network,” In Proc. of VLDB, vol. 4, no. 11, pp. 807–818, 2011. [36] E. N. Gilbert, “Random graphs,” Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959. [37] P. N. Krivitsky, “Exponential-family random graph models for valued networks,” Electronic Journal of Statistics, vol. 6, pp. 1100–1128, 2012. [38] J. Yang and J. Leskovec, “Defining and evaluating network communities based on groundtruth,”In Proc. of ICDM, 2012. [39] B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi, “On the evolution of user interaction in facebook,” In WOSN, 2009. [40] P. Erdos and A. Renyi, “On random graphs,” I. Publicationes Mathematicae, vol. 6, pp. 290–297, 1959. [41] P. Sarkar and A. Moore, “Dynamic social network analysis using latent space models,” In Proc. of SIGKDD Explorations: Special Edition on Link Mining, 2005. [42] A. Cakmak and G. Ozsoyoglu, “Mining biological networks for unknown pathways,” Bioinformatics, vol. 23, no. 20, pp. 2775–2783, 2007. [43] U. Leser, “A query language for biological networks,” In Proc. Bioinformatics, vol. 21, pp. ii33–ii39, 2005. [44] W. H. Tian and N. F. Samatova, “Global alignment of pairwise protein interaction networks for maximal common conserved patterns,” International Journal of Genomics, 2013. [45] A. Ratkiewicz and T. N. Truong, “Application of chemical graph theory for automated mechanism generation,” J. Chem. Inf. Comput. Sci., vol. 43, no. 1, pp. 36–44, 2003. [46] M. Fiedler and C. Borgelt, “Support computation for mining frequent subgraphs in a single graph,” In Proc. MLG, 2007. [47] “The ER model source code,” http://www.cs.purdue.edu/homes/dgleich/demos/erdos renyi/. [48] M. Kuramochi and G. Karypi, “Finding frequent patterns in a large sparse graph. data mining and knowledge discovery,” In Proc. of Data Mining and Knowledge Discovery, no. 11, pp. 243–271, 2005. [49] J. Prins, J. Yang, J. Huan, andW. Wang, “Spin: Mining maximal frequent subgraphs from graph databases,” In Proc. of KDD, pp. 581–586, 2004. [50] X. Yan and J. Han, “gspan: Graph-based substructure pattern mining,” In Proc. of ICDM, pp. 721–724, 2002. [51] ——, “Closegraph: Mining closed frequent graph patterns,” In Proc. of KDD, pp. 286–295, 2003. [52] C. Borgelt, T. Meinl, and M. Berthold, “Moss: A program for molecular substructure mining,” In Proc. of OSDM, 2005. [53] L. Holder, D. Cook, and S. Djoko, “Substructure discovery in the subdue system,” In Proc. of KDD, pp. 169–180, 1994. [54] P. W. Holland and S. Leinhardt, “An exponential family of probability distributions for directed graphs,” Journal of the American Statistical Association, 1981. [55] M. E. J. Newman, “Random graphs as models of networks,” in Handbook of Graphs and Networks: From the Genome to the Internet. Wiley-VCH, 2003. [56] O. Sandberg, “Neighbor selection and hitting probability in small-world graphs,” Annals of Applied Probability, vol. 18, no. 5, pp. 1771–1793, 2008. [57] P. Krivitsky, M. S. Handcock, A. E. Raftery, and P. Hoff, “Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models.” Department of Statistics, University of Washington, 2007. [58] A. L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, pp. 509–512, 1999. [59] “The Kronecker graph model source code (snap library),” http://snap.stanford.edu. [60] M. Deutsch and H. B. Gerard, “A study of normative and informational social influences upon individual judgment,” J. Abnormal and Social Psychology, vol. 51, no. 3, pp. 291–301, 1955. [61] M. F. Kaplan and C. E. Miller, “Group decision making and normative versus informational influence: Effects of type of issue and assigned decision rule,” Journal of Personality and Social Psychology, vol. 53, no. 2, pp. 306–313, 1987. [62] A. Clauset, C. R. Shalizi, and M. E. J. Newman, “Power-law distributions in empirical data,” In SIAM, vol. 51, no. 4, pp. 661–703, 2009. [63] A. Mislove, B. Viswanath, K. P. Gummadi, and P. Druschel, “You are who you know: Inferring user profiles in online social networks,” In WSDM, pp. 251–260, 2010. [64] V. Chaoji, S. Ranu, R. Rastogi, and R. Bhatt, “Recommendations to boost content spread in social networks,” In WWW, pp. 529–538, 2012. [65] D. N. Yang, W. C. Lee, N. H. Chia, M. Ye, and H. J. Hung, “Bundle configuration for spread maximization in viral marketing via social networks,” In CIKM, pp. 2234–2238, 2012. [66] M. Ye, X. Liu, and W. C. Lee, “Exploring social influence for recommendation - a probabilistic generative model approach,” In SIGIR, pp. 671–680, 2012. [67] M. Mitzenmacher and E. Upfal, “Probability and computing: Randomized algorithms and probabilistic analysis.” Cambridge University Press, 2005. [68] C. H. Chen, E. Yucesan, L. Dai, and H. C. Chen, “Efficient computation of optimal budget allocation for discrete event simulation experiment,” IIE Transactions, vol. 42, no. 1, pp. 60–70, 2010. [69] U. Feige, D. Peleg, and G. Kortsarz, “The dense k-subgraph problem,” Algorithmica, vol. 29, no. 3, pp. 410–421, 2001. [70] C. Wilson, B. Boe, A. Sala, K. P. N. Puttaswamy, and B. Y. Zhao, “User interactions in social networks and their implications,” In Eurosys, pp. 205–218, 2009. [71] E. Gilbert and K. Karahalios, “Predicting tie strength with social media,” In CHI, pp. 211–220, 2009. [72] C. Li and M. Shan, “Team formation for generalized tasks in expertise social networks,” In SocialCom, pp. 9–16, 2010. [73] M. Kargar and A. An, “Discovering top-k teams of experts with/without a leader in social networks,” In CIKM, pp. 985–994, 2011. [74] A. Gajewar and A. D. Sarma, “Multi-skill collaborative teams based on densest subgraphs,” In SDM, pp. 165–176, 2012. [75] U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, and D. Wagner, “On modularity clustering,” IEEE Transactions on Knowledge and Data Engineering, vol. 20, pp. 172–188, 2008. [76] M. Sozio and A. Gionis, “The community-search problem and how to plan a successful cocktail party,” In KDD, pp. 939–948, 2010. [77] D. F. Gleich and C. Seshadhri, “Vertex neighborhoods, low conductance cuts, and good seeds for local community methods,” In KDD, pp. 597–605, 2012. [78] M. T. Hajiaghayi and K. Jain, “The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema,” In Proc. SODA, 2006. [79] A. Krause and D. Golovin, “Submodular function maximization,” in Tractability: Practical Approaches to Hard Problems (to appear). Cambridge University Press, 2014. [80] L. Dai, C. H. Chen, and J. R. Birge, “Large convergence properties of two-stage stochastic programming,” J. Optimization Theory and Applications, vol. 106, no. 3, pp. 489–510, 2000. [81] W. Bryc, “A uniform approximation to the right normal tail integral,” In Proc. Appl. Math. Comput., 2002. [82] R. Y. Rubinstein, “Combinatorial optimization, cross-entropy, ants and rare events,” in Stochastic Optimization: Algorithms and Applications, S. Uryasev and P. M. Pardalos, Eds. Kluwer Academic, 2001, pp. 304–358. [83] A. Costa, J. Owen, and D. P. Kroese, “Convergence properties of the cross-entropy method for discrete optimization,” Operations Research Letters, vol. 35, no. 5, pp. 573–580, 2007. [84] L. Margolin, “On the convergence of the cross-entropy method,” In Annals of Operations Research, vol. 134, pp. 201–214, 2005. [85] N. Gupta, L. Kot, S. Roy, G. Bender, J. Gehrke, and C. Koch, “Entangled queries: enabling declarative data-driven coordination,” In SIGMOD, pp. 673–684, 2011. [86] D. S. Johnson, C. R. Aragon, L. A.McGeoch, and C. Schevon, “Optimization by simulated annealing: an experimental evaluation. part i, graph partitioning,” Journal Operations Research, vol. 37, pp. 865–892, 1989. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/54122 | - |
dc.description.abstract | 隨著行動裝置與Web 2.0蓬勃發展與遍佈全球,社群網路如今變得十分熱門。像是Facebook擁有12.6億使用者、Twitter擁有5.55億使用者,社群網路已轉變成一個全世界規模之巨型資料庫。另一方面,隨著社群網路之崛起,社群網路相關研究也隨之大量浮現、日益重要。是故,在本篇博士論文中,我們研究社群網路上三個重要且根本之問題。而本篇論文於社群網路分析上面臨了三大挑戰。第一,不同於交易紀錄,社群網路上點靠著許多邊連結成不同結構,這結構使得許多問題變成NP-Hard(如本論文中第三個問題即為NP-Hard)。第二,我們同時研究社群網路上不同特性,這些特性之間會產生交互作用,必須要仔細處理。第三,社群網路計算量往往遠大於交易紀錄,因此需要仔細設計演算法與資料結構。
在本論文中,我們首先探討如何對多個社群網路做聯合採樣,並提出一個稱作品質保證多網路聯合採樣演算法,品質保證多網路聯合採樣能夠有效採樣多網路並提供採樣網路與真實網路差異之統計保證。然而,由於採樣社群網路資料變得越來越困難、現有真實資料節點數大多是百萬等級、且基於統計之圖產生器只被設計保有圖之統計性質(像是原圖之度分布、圖半徑與聚合係數)而缺乏保存頻繁標型特徵,因此我們設計一個頻繁標行保存圖產生器同時保存頻繁標型、度分布與聚合係數,且能快速產生十億規模等級之社群網路。除此之外我們也探討社交活動意願最佳化之問題,我們設計一套隨機演算法能夠快速且有效解決此問題。演算法透過理論分析能夠最佳化計算資源且找到保證近似比之解。在臉書上實作成果顯示,所設計之演算法在品質與時間上顯著贏過使用者所選取結果。 | zh_TW |
dc.description.abstract | By the popularization of the mobile phones and the developing of the Web 2.0, the online social network websites become very popular nowadays. For example, the numbers of active users on Facebook and Twitter are 1.26 billion and 550 million, respectively. On the other hand, with the emergence of Online Social Networks (OSNs), they have motivated a great deal of research on social network analysis. Therefore, in this dissertation,
we study different important and fundamental problems in social networks. The challenges faced for social network analysis are threefold. First, unlike dealing with transactions, in social networks, nodes are connected with edges and form a graph, which complicates the analysis. Therefore, many problems related to graph are NP-Hard problems (as the third problem studied in this dissertation is). Second, our study considers the graph properties in social networks, in which we need to carefully address the interplay between social network properties. Third, the computation needed is much greater than the transaction case, which demands carefully designed data structures and algorithms. In this study, we first explore the joint sampling of multiple OSNs and propose an approach called Quality-guaranteed Multi-network Sampler (QMSampler) that can crawl and jointly sample multiple OSNs. QMSampler provides a statistical guarantee on the difference between the crawled real dataset and the ground truth (the perfect integration of all OSNs). Afterward, since nowadays most available real datasets only support millions of nodes and current popular statistical graph generators are properly designed to preserve only the statistical metrics, such as the degree distribution, diameter, and clustering coefficient of the original social graphs without considering the importance of frequent graph patterns, we make the first attempt to design a Pattern Preserving Graph Generation (PPGG) algorithm to generate a graph including all frequent patterns and three most popular statistical parameters: degree distribution, clustering coefficient, and average vertex degree. In addition, given the available social network datasets, we also explore the group formations with willingness optimization for social group activity. We design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T02:40:55Z (GMT). No. of bitstreams: 1 ntu-104-D99942020-1.pdf: 1952306 bytes, checksum: 212c126120d362e9f2d7acc427849e41 (MD5) Previous issue date: 2015 | en |
dc.description.tableofcontents | 1 Introduction 5
1.1 Motivation and Overview of the Dissertation . . . . . . . . . . . . . . . . . . . 5 1.1.1 Social Network Joint Sampling . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Social Network Generation . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Social Network Application . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 QMSampler: Joint Sampling of Multiple Networks with Quality Guarantee 9 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Sampling Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Non-Overlap Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Overlap Sampling with An AccurateMatching Oracle . . . . . . . . . . 19 2.3.3 Overlap Sampling with a Practical Matching Oracle . . . . . . . . . . 24 2.3.4 Random Walk Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 QMSampler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4.1 Size-Constrained Sampling . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4.2 Quality-Constrained Sampling . . . . . . . . . . . . . . . . . . . . . . 33 2.4.3 Time-Constrained Sampling . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.4 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.5 Three and More Networks . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.5.1 User Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.2 Sampling DBLP and MS . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.5.3 Synthetic Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.5.4 Crawling Flickr, Foursquare and Twitter . . . . . . . . . . . . . . . . . 44 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3 On Pattern Preserving Graph Generation 48 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2.2 Pattern Preserving Graph Generation Algorithm . . . . . . . . . . . . . 52 3.3 Pattern Preserving Phase of PPGG . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3.1 Concept Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3.2 Overlapping Process . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 Graph Augmentation Phase of PPGG . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.2 Clustering Coefficient . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.5.2 Comparison of Real Datasets and Generated Graphs . . . . . . . . . . 64 3.5.3 Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4 Willingness Maximization for Social Group Activity 69 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2.3 Integer Programming for WASO . . . . . . . . . . . . . . . . . . . . . 76 4.3 Algorithm Design for WASO . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.3.1 Allocation of Computational Budget for Start Nodes . . . . . . . . . . 79 4.3.2 Theoretical Result of CBAS with Uniform Distribution . . . . . . . . . 80 4.3.3 Theoretical Result of CBAS with Gaussian Distribution . . . . . . . . 85 4.4 Neighbor Differentiation in Randomization . . . . . . . . . . . . . . . . . . . 86 4.4.1 Greedy Neighbor Differentiation . . . . . . . . . . . . . . . . . . . . . 86 4.4.2 Neighbor Differentiation with Cross Entropy . . . . . . . . . . . . . . 86 4.4.3 Theoretical Result of CBAS-ND . . . . . . . . . . . . . . . . . . . . . 88 4.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.5.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.5.2 User Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.5.3 Performance Comparison and Sensitivity Analysis . . . . . . . . . . . 95 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5 Summaries and Future Work 99 Appendices 102 A Theoretical Results for Greedy Algorithms . . . . . . . . . . . . . . . . . . . . 102 B Willingness Optimization for Non-fixed Group Size . . . . . . . . . . . . . . . 105 C Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 D Parameter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 E Illustrative Examples and Complexity Analysis . . . . . . . . . . . . . . . . . 108 E.1 Example and Time Complexity of CBAS . . . . . . . . . . . . . . . . 108 E.2 Example and Time Complexity of CBAS-ND . . . . . . . . . . . . . . 109 F Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 F.1 Online computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 F.2 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 F.3 CBAS-ND for Different Scenarios . . . . . . . . . . . . . . . . . . . . 111 G Supplementary experimental results on the Facebook dataset . . . . . . . . . . 111 H Pseudo Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 | |
dc.language.iso | en | |
dc.title | 社群網路取樣、產生與應用 | zh_TW |
dc.title | Sampling, Generation, and Application of Social Networks | en |
dc.type | Thesis | |
dc.date.schoolyear | 103-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 陳良弼(Arbee Liang-Pi Chen),曾新穆(Vincent Shin-Mu Tseng),張嘉惠(Chia-Hui Chang),楊得年(De-Nian Yang) | |
dc.subject.keyword | 演算法設計與分析,詢問處理,社群網路,近似演算法,資料產生, | zh_TW |
dc.subject.keyword | Algorithm Design and Analysis,Query Processing,Social Networks,Approximation Algorithm,Data Generation, | en |
dc.relation.page | 124 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2015-07-22 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
顯示於系所單位: | 電信工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 1.91 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。