請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63166
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林守德(Shou-De Lin) | |
dc.contributor.author | Cheng-Te Li | en |
dc.contributor.author | 李政德 | zh_TW |
dc.date.accessioned | 2021-06-16T16:25:58Z | - |
dc.date.available | 2018-02-01 | |
dc.date.copyright | 2013-02-01 | |
dc.date.issued | 2013 | |
dc.date.submitted | 2013-01-21 | |
dc.identifier.citation | [1] 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, 2006.
[2] L. Akoglu and C. Faloutsos. RTG: A Recursive Realistic Graph Generator Using Random Typing. In Proceedings of European Conference on Principles of Data Mining and Knowledge Discovery (PKDD’09), 13-28, 2009. [3] L. Akoglu, M. Mcglohon, and C. Faloutsos. RTM: Laws and A Recursive Generator for Weighted Time Evolving Graphs. In Proceedings of IEEE International Conference on Data Mining (ICDM’08), 701-706, 2008. [4] M. Aoyagi and A. Namatame. Synchronization in Mobile Agents and Effects of Network Topology. Journal of Agent-Based Social Systems, 6(3), 31-42, 2009. [5] A. L. Barabasi, and R. Albert. Emergence of Scaling in Random Networks. Science 286(5439), 509-512, 1999. [6] S. Bhagat, A. Goyal, and L. V. S. Lakshmanan. Maximizing Product Adoption in Social Networks. In Proceedings of ACM International Conference on Web Search and Data Mining (WSDM’12), 603-612, 2012. [7] S. Bharathi, D. Kempe, and M. Salek. Competitive Influence Maximization in Social Networks. In Proceedings of International Conference on Internet and Network Economics (WINE’07), 306-311, 2007. [8] M. E. F. Bloch. How we Think They Think: Anthropological Approaches to Cognition, Memory, and Literacy. Boulder, Colo.: Westview Press, 1998. [9] M. E. F. Bloch. The Past and the Present in the Present. Man, New Series, 12(2), 278-292, 1977. [10] C. Budak, D. Agrawal, and A. E. Abbadi. Limiting the Spread of Misinformation in Social Networks. In Proceedings of ACM International World Wide Web Conference (WWW’11), 665-674, 2011. [11] K. E. Campbell. Networks Past: a 1939 Bloomington Neighborhood. Social Forces, 69(1), 139-155, 1990. [12] D. Chakrabarti and C. Faloutsos. Graph Mining: Laws, Generators, and Algorithms. ACM Computing Survey, 38(1), 2006. [13] W. M. Chao and T. Y. Li. Simulating Crowd Behaviors with a Communication Model. In Proceedings of International Conference on Computer Animation and Social Agents (CASA’08), 2008. [14] V. Chaoji, S. Ranu, R. Rastogi, and R. Bhatt. Recommendations to Boost Content Spread in Social Networks. In Proceedings of ACM International World Wide Web Conference (WWW’12), 529-538, 2012. [15] C. Chen, X. Yan, F. Zhu, and J. Han. gApprox: Mining Frequent Approximate Patterns from a Massive Network. In Proceedings of IEEE International Conference on Data Mining (ICDM’07), 445-450, 2007. [16] 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. [17] W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rincon, X. Sun, Y. Wang, W. Wei, and Y. Yuan. Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate. In Proceedings of SIAM International Conference on Data Mining (SDM’11), 379-390, 2011. [18] W. Chen, W. Lu, and N. Zhang. Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process. In Proceedings of AAAI International Conference on Artificial Intelligence (AAAI’12), 2012. [19] W. Chen, C. Wang, and Y. Wang. Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’10), 1029-1038, 2010. [20] W. Chen, Y. Wang, and S. Yang. Efficient Influence Maximization in Social Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09), 199-208, 2009. [21] W. Chen, Y. Yuan, and L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In Proceedings of IEEE International Conference on Data Mining (ICDM’10), 88-97, 2010. [22] L. Cheng and R. C.-W. Wong. Minimizing Seed Set for Viral Marketing. In Proceedings of IEEE International Conference on Data Mining (ICDM’11), 427-436, 2011. [23] S. Chenney. Flow Tiles. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’04), 233-242, 2004. [24] Howie Choset. Robotic Motion Planning: Potential Functions. Lecture slides of motion planning, Robotics Institute 16-735. [25] A. Clauset, M.E.J. Newman and C. Moore. Finding Community Structure in Very Large Networks. Physical Review E 70, 066111, 2004. [26] D. Cosley, D. Huttenlocher, J. Kleinberg, X. Lan, and S. Suri. Sequential Influence Models in Social Networks. In Proceedings of AAAI International Conference on Weblogs and Social Media (ICWSM’10), 2010. [27] P. Domingos and M. Richardson. Mining the Network Value of Customers. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’01), 57-66, 2001. [28] D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010. [29] B. Edmonds. How Are Physical and Social Spaces Related? – Cognitive Agents as the Necessary “Glue”. Journal of Agent-based Computational Modeling, 195-214, 2006. [30] D. Erdos, V. Ishakian, A. Lapets, E. Terzi, and A. Bestavros. The Filter-Placement Problem and Its Application to Minimizing Information Multiplicity. In Proceedings of the VLDB Endowment (PVLDB), 5(5), 418-429, 2012. [31] P. Erdos and A. Renyi. On Random Graphs. Mathematicae, 6, 290-297, 1959. [32] M. Ester and H. Kriegel, J. Sander, and X. Xu. A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’96), 226-231, 1996. [33] M. Field. Algebraic Connectivity of Graphs. Journal of Czechoslovak Math, 23, 298-305, 1973. [34] L. C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry, 40(1), 35-41, 1977. [35] N. E. Friedkin. A Structural Theory of Social Influence. Cambridge University Press, 1998. [36] M. Girvan and M. E. J. Newman. Community Structure in Social and Biological Networks. In Proceedings of National Academic of Sciences (PNAS’02). 7821-7826, 2002. [37] J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A Complex Systems Look at the Underlying Process of word-of-mouth. Marketing Letters, 12(3), 211-223, 2001. [38] M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring Networks of Diffusion and Influence. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’10), 1019-1028, 2010. [39] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. A Data-Based Approach to Social Influence Maximization. In Proceedings of the VLDB Endowment (PVLDB), 5(1), 73-84, 2012. [40] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Learning Influence Probabilities in Social Networks. In Proceedings of ACM International Conference on Web Search and Data Mining (WSDM’10), 241-250, 2010. [41] A. Goyal, W. Lu, and L. V. S. Lakshmanan. Simpath: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In Proceedings of IEEE International Conference on Data Mining (ICDM’11), 211-220, 2011. [42] A. Goyal and L. V. S. Lakshmanan. RecMax: Exploiting Recommender Systems for Fun and Profit. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’12), 1294-1302, 2012. [43] M. Granovetter. Threshold Models of Collective Behavior. American Journal of Sociology, 83(6), 1420-1443, 1978. [44] L. Hamill and N. Gilbert. Social Circles: A Simple Structure for Agent-Based Social Network Models. Journal of Artificial Societies and Social Simulation, 12(2), 3, 2009. [45] D. Helbing, J. Farkas, and T. Vicsek. Simulating Dynamical Features of Escape Panic. Nature 407, 487-490, 2000. [46] I. Hodder and C. Orton. Spatial Analysis in Archaeology. Cambridge University Press, Cambridge, 1976. [47] Y. K. Hwang and N. Ahuja. A Potential Field Approach to Path Planning. IEEE Transactions on Robotics and Automation, 8(1), 23-32, 1991. [48] 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. [49] D. Kempe, J. M. Kleinberg, and E. Tardos. Maximizing the Spread of Influence through a Social Network. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’03), 137-146, 2003. [50] B.W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49(1), 291-307, 1970. [51] M. Kimura and K. Saito. Tractable Models for Information Diffusion in Social Networks. In Proceedings of European Conference on Principles of Data Mining and Knowledge Discovery (PKDD’06), 259-271, 2006. [52] M. Kimura, K. Saito, and H. Motoda. Blocking Links to Minimize Contamination Spread in a Social Network. ACM Transactions on Knowledge Discovery from Data (TKDD), 3(2): 9, 2009. [53] M. Lahiri and T. Y. Berger-wolf. Mining Periodic Behavior in Dynamic Social Networks. In Proceedings of IEEE International Conference on Data Mining (ICDM’08), 373-382, 2008. [54] T. Lappas, E. Terzi, D. Gunopulos, and H. Mannila. Finding Effectors in Social Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’10), 1059-1068, 2010. [55] J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos. Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication. In Proceedings of European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD’05), 133-145, 2005. [56] J. Leskovec and C. Faloutsos. Scalable Modeling of Real Graphs Using Kronecker Multiplication. In Proceedings of International Conference on Machine Learning (ICML’07), 497-504, 2007. [57] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective Outbreak Detection in Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’07), 420-429, 2007. [58] J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney. Statistical Properties of Community Structure in Large Social and Information Networks. In Proceedings of ACM International World Wide Web Conference (WWW’08), 695-704, 2008. [59] J. Leskovec, K. Lang, and M. Mahoney. Empirical Comparison of Algorithms for Network Community Detection. In Proceedings of ACM International World Wide Web Conference (WWW’10), 631-640, 2010. [60] J. Leskovec, J. M. Kleinberg, and C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’05), 177-187, 2005. [61] H. Ma, H. Yang, M. R. Lyu, and I. King. Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection. In Proceedings of ACM International Conference on Knowledge and Information Management (CIKM’08), 233-242, 2008. [62] R. H. MacArthur. Geographical Ecology: Patterns in the Distribution of Species. Princeton University Press, 1984. [63] C. D. Manning, P. Raghavan, and H. Schutze. Introduction to Information Retrieval: Evaluation of Clustering. Cambridge University Press, 2008. [64] M. Mathioudakis, F. Bonchi, C. Castillo, A. Gionis, and A. Ukkonen. Sparsification of Influence Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’11), 529-537, 2011. [65] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology, 27, 415-444, 2001. [66] S. Myers, C. Zhu, and J. Leskovec. Information Diffusion and External Influence in Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’12), 33-41, 2012. [67] M. E. J. Newman. Random Graphs as Models of Networks. Handbook of Graphs and Networks: From the Genome to the Internet, Wiley-VCH, Berlin, 35-68, 2003. [68] M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review, 45(2), 2003. [69] M. E. J. Newman. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E 69, 066133, 2004. [70] R. Neumann and F. Strack. Mood Contagion: The Automatic Transfer of Mood between Persons. Journal of Personality and Social Psychology, 79(2), 211-223, 2000. [71] N. Pelechano, J. M. Allbeck, and N. I. Badler. Controlling Individual Agents in High-Density Crowd Simulation. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’07), 99-108, 2007. [72] N. Pelechano and N. I. Badler. Modeling Crowd and Trained Leader Behavior during Building Evacuation. IEEE Computer Graphics and Applications, 26(6), 80-86, 2007. [73] P. Pons and M. Latapy. Computing Communities in Large Networks Using Random Walks. Journal of Graph Algorithms and Applications, 10(2), 191-218, 2006. [74] U. N. Raghavan, R. Albert, and S. Kumara. Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks. Physical Review E 76, 03610, 2007. [75] C. W. Reynolds. Flocks, Herds and Schools. A Distributed Behavior Model. In Proceedings of ACM SIGGRAPH International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’87), 25-34, 1987. [76] M. Richardson and P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’02), 61-70, 2002. [77] M. Rosvall and C. Bergstrom. Maps of Random Walks on Complex Networks Reveal Community Structure. In Proceedings of National Academic of Sciences (PNAS’08), 1118-1123, 2008. [78] K. Saito, R. Nakano, and M. Kimura. Prediction of Information Diffusion Probabilities for Independent Cascade Model. In Proceedings of International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES’08), 67-75, 2008. [79] 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. [80] A. Schadschneider, W. Klingsch, H. Klupfel, T. Kretz, C. Rogsch, and A. Seyfried. Evacuation Dynamics: Empirical Results, Modeling and Applications. Encyclopedia of Complexity and Systems Science, 3142-3176, 2009. [81] J. Scripps, P.-N. Tan, and A.-H. Esfahanian. Node Roles and Community Structure in Networks. In Proceedings of ACM SIGKDD International Workshop on Social Network Analysis (SNA-KDD), 26-35, 2007. [82] W. Shao and D. Terzopoulos. Autonomous Pedestrians. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer animation (SCA’05), 19-28, 2005. [83] Y. Singer. How to Win Friends and Influence People, Truthfully: Influence Maximization Mechanisms for Social Networks. In Proceedings of ACM International Conference on Web Search and Data Mining (WSDM’12), 733-742, 2012. [84] M. Slatkin. Gene Flow and the Geographic Structure of Natural Populations. Science, 236(4803), 787-792, 1987. [85] H. Sun, J. Huang, J. Han, H. Deng, P. Zhao, and B. Feng. gSkeletonClu: Density-based Network Clustering via Structure-Connected Tree Division or Agglomeration. In Proceedings of IEEE International Conference on Data Mining (ICDM’10), 481-490, 2010. [86] H. Takahashi and A. Matsuyama. An Approximate Solution for the Steiner Problem in Graphs. Mathematica Japonica, 24, 573-577, 1980. [87] T. Thurston. The location of Power and the Art of Resistance: Spatial Analysis and Social Theory in Regional Archaeology. In Space—Archaeology’s Final Frontier? An Intercontinental Approach. Roderick B. Salisbury and Dustin Keeler, eds. Newcastle, UK: Cambridge Scholars Publishing, 158-191, 2007. [88] H. Tong and C. Faloutsos. Center-Piece Subgraph: Problem Definition and Fast Solutions. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’06), 404-413, 2006. [89] H. Tong, C. Faloutsos, and J.-Y. Pan. Fast Random Walk with Restart and its Applications. In Proceedings of IEEE International Conference on Data Mining (ICDM’06), 613-622, 2006. [90] A. Treuille, S. Cooper, and Z. Popovic. Continuum Crowds. ACM Transactions on Graphics, 25(3), 1160-1168, 2006. [91] Y. Wang, G. Cong, G. Song, and K. Xie. Community-based Greedy Algorithm for Mining Top-k Influential Nodes in Mobile Social Networks. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’10), 1039-1048, 2010. [92] S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, 1994. [93] D. J. Watts and S. H. Strogatz. Collective Dynamics of ‘Small-world’ Networks. Nature, 393, 440-442, 1998. [94] S. Wolfram. Theory and Applications of Cellular Automata. Advanced Series on Complex Systems, Singapore: World Scientific Publication, 1986. [95] 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. [96] J. Yang and J. Leskovec. Modeling Information Diffusion in Implicit Networks. In Proceedings of IEEE International Conference on Data Mining (ICDM’10), 599-608, 2010. [97] H. Yeh, S. Curtis, S. Patil, J. V. D. Berg, D. Manocha, and M. Lin. Composite Agents. In Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’08), 39-47, 2008. [98] W. W. Zachary. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 33(4), 452-473, 1977. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63166 | - |
dc.description.abstract | 社群網路(Social Network)描述真實世界中人與人之間各種社交關係,隨著社群網路服務的崛起,如Facebook、Twitter與Foursquare,社交資料已變得容易取得,傳統社群網路分析之問題,如分析重要節點、偵測網路社群(Network Community)與社群網路生成模型,已逐漸被徹底探討與研究。本論文試圖從兩個嶄新的角度來進行社群網路探勘。(a)社群結構在時間空間下之動態變化:人和人之間的社交連結與人們在地理空間上群聚移動之行為,這二者之間是否存在關聯性?(b)資訊於社交個體間之傳播動態:對於不同情境的影響力擴散,哪些個體對於資訊的流通扮演最關鍵的角色?
人類學家、生物學家與社會學家之研究已指出社群網路之形成乃是人們在地理空間上實際交流與互動之結果,地理位置相距較近之個體能擁有較多的機會彼此物理聯繫,進而發展社交關係。本論文的第一部分在於結合人群模擬之技術(Crowd Simulation)與社群網路分析,試圖從電腦模擬計算之角度來捕捉並分析個體間的社交連結與他們在空間中群聚移動此二者間之關係,以驗證該科學假說。我們設計了一個社交人群模擬之架構Social Flocks,其核心概念在於將人群模擬地理空間中的每個代理人對應至社群網路中的一個社交個體,並透過代理人彼此間的物理交互作用力來實現社交群聚移動之效果。在Social Flocks架構下,我們完成了四個任務,其中前二者之目的在於完成該科學驗證,後二者則為基於社交人群模擬之應用。(1)我們透過社交人群模擬來自動生成具備真實世界社群網路之特性(如:個體間之高群聚性、低平均路徑距離、與具冪次法則之分支度)之合成網路;(2)給定一社群網路,我們利用個體代理人於地理空間中移動之軌跡來偵測網路社群。此二任務之實驗結果驗證了該科學假說:個體於空間中之物理互動與群體移動能夠形成真實社群網路並自然產生社群。(3)我們將社群網路引進人群模擬,藉以產生真實世界社交互動之各種人群集體移動行為。(4)我們結合社群網路與人群逃生,模擬出更為真實的社交逃生行為,並自動規劃出口以及逃生號誌之位置,以改進災難發生時,個體逃生之最終存活率。 在社群網路上,個體彼此間最普遍的互動行為即是資訊的交流與傳遞,任何資訊皆有機會透過社交連結在社群網路中廣為傳播,而病毒式行銷正是這種社群網路上個體間影響力擴散(Influence Propagation)的最佳應用。基於影響力擴散之設定,本論文之第二部分試圖針對真實世界五種不同的應用情境,透過影響力擴散機制之模擬,找出社群網路上,對影響力最大化扮演各種最關鍵角色之個體:(1)哪些個體掌握著資訊擴散之瓶頸?(2)哪些個體可使得目標市場行銷獲得最大效益?(3)當社群網路隨著時間而成長變動時,哪些個體對於影響力最大化最為有效?(4)如何整合直銷與病毒式行銷,以獲得更大行銷效益?(5)在考慮個體間各種異質性關係的狀況下,如何設計影響力傳播之機制並達到影響力最大化?針對這五個問題,我們設計對應的演算法,並實驗於真實社群網路資料,結果顯示對於各種影響力擴散之情境,在影響力最大化之設定下,我們所提出之方法皆能有不錯的效能表現。 | zh_TW |
dc.description.abstract | Social networks depict the interactions between people in the real world. With the bloom of social networking services, such as Facebook, Twitter, and Foursquare, social topology has been investigated every hole and corner, ranging from entity resolution to group identification and social network generation modeling in either static or dynamic points of view. In this thesis, we propose to study the social interactions between people from two novel perspectives: (a) the spatial-temporal dynamics of social structures: what is the potential relationship between social connections and collective moving behaviors of crowds in the geographical space? (b) The influence dynamics over social actors: which nodes are the most critical ones under different scenarios of influence propagation?
Scientific studies from anthropologists, biologists, and sociologists have hypothesized that the formation of social structures usually resulted from the spatial-temporal interactions between individuals, as people who live in the geospatial neighborhood have more chances to physically contact with each other and construct the social relationships. The first part of this thesis brings a marriage of crowd simulation and social network analysis to verify such scientific hypothesis by unveiling the connection between the spatial-temporal movements of people and their social relationships. We exploit the crowd simulation to accomplish the spatial-temporal dynamics of social elements by associating each node in the social network with one agent in the space. A social simulation framework, Social Flocks, is developed to deal with four tasks. The first two tasks are designed to verify the scientific hypothesis while the last two are application based on social crowd simulation. (1) We aim to generate realistic social networks that satisfy network properties (e.g. high clustering coefficient, low average path length, and power-law degree distribution). (2) Given a social network, we aim at detecting network communities based on the social moving trajectories of nodes. Experimental results on these two tasks verify the scientific hypothesis that the movement and physical interaction among people can indeed lead to the formulation of a social network as well as the communities. (3) We impose the social connections between agents into produce realistic collective social behaviors over crowds. (4) We consider social factors to study the evacuation dynamics and automatically facilitate the spatial deployment of exit determination and sign placement for improving the survival rate. One of the most common actions between individuals in social networks is information exchange and diffusion. Any digital contents could be propagated around the social network through social connections. Viral marketing is one of the well-known applications of such influence propagation phenomenon. In the second part, we consider the information diffusion over individuals as well as influence maximization in a social network as the fundamental to identify nodes which play crucial roles under diverse kinds of real-world marketing scenarios. Through simulating how influence is propagated over individuals, we propose and tackle five various but novel marketing problems: (1) How to locate those individuals that hold the bottlenecks of influence propagation? (2) Can we discover the effective seed individuals for targeted advertising? (3) Which nodes are the influential seeds for starting the propagation in a dynamic social network? (4) How to integrate the ideas of direct selling and viral marketing? (5) Can we devise the propagation mechanism over heterogeneous social networks for influence maximization? Experiments conducted on real social networks demonstrate the promising performance of the proposed approaches on enhancing the effectiveness of influence propagation. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T16:25:58Z (GMT). No. of bitstreams: 1 ntu-102-D98944005-1.pdf: 3739131 bytes, checksum: fac143e73a6894ddf456fe2429a838c3 (MD5) Previous issue date: 2013 | en |
dc.description.tableofcontents | 口試委員會審訂書 i
誌謝 iii 中文摘要 vii Abstract ix Contents xi List of Figures xv List of Tables xix Chapter 1 Introduction 1 1.1. Motivation and Impacts 1 1.2. Overview and Problem Statements 3 1.3. Main Contributions 7 1.4. Thesis Organization 11 Chapter 2 Modeling Social Networks by Crowd Simulation 13 2.1. Introduction 13 2.2. Related Work 15 2.3. Preliminary 16 2.4. Touch Model 18 2.5. Neighborhood-Density Model 19 2.6. Explorer Model 21 2.7. Advanced Network Properties 25 2.8. Short Summary 26 Chapter 3 Simulating Crowds for Network Community Detection 28 3.1. Introduction 28 3.2. Related Work 30 3.3. Acquaintance Force 30 3.4. Trajectory-based Community Identification 34 3.5. Experiments 37 3.5.1. Network Datasets 38 3.5.2. Evaluation Criteria 39 3.5.3. Visualizaing Crowdstering Results 41 3.5.4. Comparison to Conventional Community Detection Methods 42 3.5.5. Sensitivity Test of Parameters 46 3.6. Short Summary 49 Chapter 4 Social-based Crowd Simulation 52 4.1. Introduction 52 4.2. Related Work 56 4.3. Simulating Collective Social Behaviors 57 4.3.1. Community-Guided Flocking 58 4.3.2. Leader Following 58 4.3.3. Spatial-Social Information Propagation 60 4.4. Information Diffusion over Social Crowds 60 4.4.1. Diffusion Method 60 4.4.2. Targeted Spreading 61 4.4.3. Experimental Results 62 4.5. Social Evacuation Planning 64 4.5.1. System Framework 64 4.5.2. Intelligent Design of Exits and Signs 65 4.5.3. Simulation of Fire Evacuation 68 4.5.4. Evaluation 69 4.5.5. Demonstration 72 4.6. Short Summary 73 Chapter 5 Mining Influence Propagation in Social Networks 75 5.1. Introduction 75 5.2. Background and Related Work 79 5.2.1. Influence Propagation Models 79 5.2.2. Influence Maximization 80 5.2.3. Finding Diverse Roles under Influence Propagation 82 5.3. Influential Mediators 84 5.3.1. Problem Statement 84 5.3.2. Solution to k-Mediator Problem 85 5.3.3. Experimental Results 87 5.4. Targeted Influencers 88 5.4.1. Problem Statement 88 5.4.2. Solution to Target-Influencer Problem 89 5.4.3. Experimental Results 90 5.5. Seed Successors 91 5.5.1. Problem Statement 91 5.5.2. Solution to Seed-Successor Problem 92 5.5.3. Experimental Results 94 5.6. Dynamic Influence Activation 96 5.6.1. Dynamic Target Selection 96 5.6.2. Target Selection Strategy 97 5.6.3. Experimental Results 98 5.7. Influence on Heterogeneous Social Networks 100 5.7.1. Problem Statement 101 5.7.2. Solution to Heterogeneous Influence Modeling 102 5.7.3. Experimental Results 104 Chapter 6 Conclusions 105 Bibography 108 | |
dc.language.iso | en | |
dc.title | 基於人群模擬與影響力擴散之社群網路探勘 | zh_TW |
dc.title | Mining Social Networks from the Perspectives of Crowd Simulation and Influence Propagation | en |
dc.type | Thesis | |
dc.date.schoolyear | 101-1 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 陳銘憲(Ming-Syan Chen),李素瑛(Suh-Yin Lee),許聞廉(Wen-Lian Hsu),陳良弼(Arbee L.P. Chen),曾新穆(Vincent S. Tseng) | |
dc.subject.keyword | 社群網路,資料探勘,人群模擬,影響力擴散,資訊擴散,社群網路生成,網路社群偵測,逃生規劃,病毒式行銷,影響力最大化, | zh_TW |
dc.subject.keyword | social network,data mining,crowd simulation,influence propagation,information diffusion,social network generation,community detection,evacuation planning,viral marketing,influence maximization, | en |
dc.relation.page | 115 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2013-01-21 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 3.65 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。