선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 기존 연구결과를 살펴보았을 때 대규모 소셜 네트워크를 효과적으로 분석하기 위해서는 알고리즘의 확장성을 높이는 것이 중요한데, 여기서 중요한 요소인 계산 복잡도 측면에서 아직 극복해야 할 난제가 많다. 소셜 네트워크에 대한 연구의 궁극적인 목적은 소셜 네트워크의 구조 및 정보 확산 현상을 규명하고 이를 다양한 분야에 응용하여 사회적 이익을 창출하는 것이다. 이를 위해서는 규모가 큰 실세계 네트워크에 적용 가능한 알고리즘이 반드시 필요하다.
- 있다. 실제 네트워크를 보다 정확하게 반영하고 다양한 분야에서 활용이 가능하게 하는 것이 이들 연구의 목표이다.
- 지금까지 소셜 네트워크의 정보 확산 패턴 및 구조분석 연구에 대한 접근법 및 머신 러닝과 데이터 마이닝 분석 기술이 접목된 연구 결과들을 살펴보았다. 기존 연구결과를 살펴보았을 때 대규모 소셜 네트워크를 효과적으로 분석하기 위해서는 알고리즘의 확장성을 높이는 것이 중요한데, 여기서 중요한 요소인 계산 복잡도 측면에서 아직 극복해야 할 난제가 많다.
가설 설정
- 먼저 네트워크 정보 확산 과정을 모델링하는 연구를 살펴보려고 한다. 알려진 연구 결과 가운데 가장 대표적인 두 가지 모델을 꼽으면 첫 번째로 Linear Threshold(LT) 모델을 들 수 있는데 Granovetter[13] 등에 의해 제안된 LT 모델은 각 노드가 이웃 노드로부터 새로운 정보를 받아들일 것인지의 여부는 해당 노드마다 정해진 문턱값(threshold)에 의해 결정된다고 가정하고 있다. 두 번째로 Independent Cascade(IC) 모델이 있는데 Goldenberg, Libai, and Muller[(2)가 제시한 이 모델은 정보가 각 링크를 통해 독립적으로 확산되는 패턴을 가진다고 보고 이에 확산 확률을 정의한다.
- 여기서는 각 노드들 사이에 유사도를 부여하고, 그 유사도가 높을수록 연결이 있을 가능성이 높다고 가정하는 것이다. 유사도 부여 방식에는 크게 두 가지 방식이 있는데, 첫 번째로 이웃 노드의 숫자를 활용한 유사도 부여 방식이다 Common Neighbors, Jaccard, Adamic/Adar[6] 유사도 방법을 대표적으로 꼽을 수 있다.
참고문헌 (28)
-
N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 1992, xiii+254 pp.
-
A. Arenas, A. Diaz-Guilera, and C. J. Perez-Vicente, Synchronization Reveals Topological Scales in Complex Networks, Phys. Rev. Lett. 96 114102, 2006.
-
L. Backstrom and J. Leskovec, Supervised Random Walks: Predicting and Recommending Links in Social Networks, In proc. of the 4th ACM WSDM conference, 2011.
-
A. Barabasi, Linked: The New Science of Networks, Perseus Publishing, April 2002.
-
S. Brin and L. Page, The Anatomy of a Large-scale Hypertextual Web Search Engine, Computer Networks and ISDN Systems, 30(1-7):107-117, 1998.
-
G. Salton and M. J. McGill. Introduction to Modem Information Retrieval, McGraw-Hill, 1983.
-
W. Chen, C. Wang, and Y. Wang, Scalable Influence Maximization for prevalent viral marketing in large scale social networks, In proc. of the 16th ACM SIGKDD, 2010.
-
Y. Sun, J. Han, J. Gao, and Y. Yu, iTopicModel: Information Network-Integrated Topic Modeling, In proc. ofthe 10th IEEE ICDM, 2009.
-
V. D. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks, J. Stat. Mech 2008(10)., P10008, 2008
-
Statistica, Number of monthly active international Twitter users from 1st quarter 2010 to 1st quarter 2014 (in millions), http://www.statista.com/statistics/274565/monthly-active-international-twitter-users/, 2014
-
J. C. Miller, Percolation and Epidemics in Random Clustered Networks, Phys. Rev. E 80, 020901, 2009.
-
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. Vol. 12, No.3, pp.211-223, 2001.
-
M. Granovetter, Threshold Models of Collective Behavior, American journal of sociology. Vol. 83, No. 6, pp.1420-1443, 1978.
-
T. Yang, R. Jin, Y. Chi, and S. Zhu, Combining Link and Content for Community Detection: a Discriminative Approach, In proc. of the 15th SIGKDD, 2009.
-
D. E. Whitney, Dynamic Theory of Cascades on Finite Clustered Random Networks with a Threshold Rule, Phys. Rev. E 82, 066110, 2010.
-
정하웅, 강병남, 복잡계 네트워크에 대한 최근 연구동향, 물리학과 첨단기술, 2007년 10월호
-
F. Kuhn, K. Panagiotou, J. Spencer, and A. Steger, Synchrony and Asynchrony in Neural Networks, In proc. of the 21st SODA, 2010.
-
B. Karrer and M. E. J. Newman, Random Graphs Containing Arbitrary Distributions of Sub graphs, Phys. Rev. E 82, 066118, 2010.
-
L. Katz. A New Status Index Derived from Sociometric Analysis, Psychometrika, 18(1):39-43, 1953.
-
D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the Spread of Influence Through a Social Network. In proc. of the 9th ACM SIGKDD, 2003.
-
J. Kleinberg, Navigation in a Small World, Nature 406:845, 2000.
-
J. Leskovec and J. Kleinberg and C. Faloutsos, Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, In proc. of the 11th ACM SIGKDD, 2005.
-
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. Van-Briesen, and N. S. Glance, Cost-effective Outbreak Detection in Networks, In proc. of the 13th ACM SIGKDD,2007.
-
M. E. J. Newman and M. Girvan, Finding and Evaluating Community Structure in Networks, Phys. Rev. E 69, 026113, 2004.
-
S. Zhu, K. Yu, Y. Chi, and Y. Gong, Combining Content and Link for Classification Using Matrix Factorization, In proc. of the 30th SIGIR, 2007.
-
B. Shaw, B. Huang and T. Jebara, Learning a Distance Metric from a Network, In proc. of the 25th NIPS, 2011.
-
S. Lim, S. Ryu, S. Kwon, K. lung and J. Lee, Link SCAN*: Overlapping Community Detection Using the Link-Space Transformation, ICDE 2014, pp292-303, 2014
-
G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature, vol. 435, pp. 814 - 818, 2005.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.