The `electronic footprints` [1] such as e-mails [2], photos [3], or phone call logs [4] that reveal much of people`s thinking process and actions have become the new sources of human activity recording in the last decade [5]. The online social networking service is the largest store that captures human activities.
Understanding structures and dynamics of online social networks, thus, is important for two reasons at least. One is because we discover human nature in the online social network, as it is a miniature of our society at a variety scale. The other is because the online social network itself is a virtual world where various phenomena emerge, such as gossip propagation, money exchange, and reputation management. Nevertheless, structures and dynamics thereof are not so simple that we cannot clearly illustrate the
whole process.
This dissertation tackles the complex structures and dynamics of online social networks by multilevel approach focusing on di erent entities from macroscopic view to microscopic view. We zoomed in on the online social networks from an entire network to a community, a dyad, and an individual. Each level has its own inherent, but complementary, resolution to capture elemental processes and guides us to understand the complex structures and dynamics as a combination of ndings across multiple levels.
We begin with the entire network structures and dynamics in Twitter. We focus on the networkwide structural properties and the information di usion process therein. Through large-scale Twitter data, we analyze the topology of the social graph, identify influentials, characterize temporal behavior of trending topics, and present the impact of retweets with regard to the number of audience. We also propose a novel method to find influentials by considering both the link structure and the temporal order of information adoption in Twitter. Then, we move on the community structure as the mesoscale units
of the network structure. We quantify the inconsistency that has been largely ignored in community identification and propose an iterative solution that improves the consistency without compromising the quality of partitioning. Next, we see more micro-scale structures and dynamics of online social networks by focusing on the dynamics of online relationship. From the two and a half years of guestbook logs from Cyworld we build and analyze a directed and weighted activity network. The directionality and the strength of activity cannot be usually observed from a friendship network widely analyzed in previous
literature. We also look into the dissolution of online relationships through the unfollow behavior in Twitter. From the follow relationships of 1.2 million Korean-speaking users over the course of 51 days and user interviews, we explore the characteristics of the unfollow behavior and motivation thereof. Finally, we look into the most fundamental unit in online social networks, an individual. We propose an algorithm based on user-labeled tags to nd others with similar interests beyond the boundary of a single service. We evaluate our algorithms with millions of tags from various web services by well-designed user study.
The strength of this dissertation lies in the robust multi-level analysis on structures and dynamics of online social networks using large-scale data. I believe that this work not only is a building block for understanding complex phenomena in online social networks, but also gives readers valuable insight into future trends of analyzing, designing, and managing online social networking services.
이메일[2]이나 사진[3], 또는 통화 내역[4]과 같은 `전자적 기록`[1]은 지난 10년간 사람의 행동을 기록하는 새로운 수단으로 주목 받고 있다[5].
그 중에서도 온라인 소셜 네트워크 서비스는 다수의 사람들의 행동을 기록하는 서비스로 인기를 모으고 있다.
이러한 온라인 소셜 네트워크의 구조와 동역학을 이해하는 것은 적어도 두 가지 이유에서 중요하다고 할 수 있다.
하나의 이유는 온라인 소셜 네트워크가 다양한 크기를 갖는 사회적 시스템으로서 사람 행동의 특성을 기록하고 발견할 수 있다는 것이다.
또 다른 하나는 온라인 소셜 네트워크 자체가 하나의 새로운 세계로 기능하며 다양한 현상, 예를 들면 소문의 전파나 경제적 교환 등이 일어난다는 것이다.
이러한 이유들에도 불구하고 온라인 소셜 네트워크의 구조와 동역학은 복잡하여 전체 과정을 이해하는 것이 쉽지 않다.
본 논문에서는 이러한 문제를 온라인 소셜 네트워크를 이루는 서로 다른 구성 요소들에 대한 다층적 접근으로 풀려고 하였다.
다층적 접근은 네트워크 전체로부터 시작해서 점차 확대해 들어가며 커뮤니티, 사회적 관계, 개인을 조명한다. 이러한 각기 다른 구성 요소들은 서로 다르면서도 상호 보완적인 시선으로 보다 근본적인 현상을 포착한다는 사실에 기초를 두고 있다. 또한 이층에서 발견된 결과들의 조합으로 복잡한 현상을 이해하게 해준다.
본 논문은 가장 거시적인 수준에서 온라인 소셜 네트워크를 바라보는 것으로 시작한다. 우리는 방향성이 있는 트위터의 팔로우 관계가 네트워크의 구조와 동역학의 특성에 어떤 영향을 미치는지 살펴보았다. 대량의 트위터 데이터로부터 네트워크의 구조를 분석하고 개인의 영향력을 측정하였으며, 널리 이야기되는 토픽의 시간적 특성을 파악하였으며 입소문을 통해 정보가 전파되는 특성을 파악하였다. 또한 네트워크의 링크 구조만이 아니라 정보 전파의 특성으로부터 사용자의 영향력을 측정하는 새로운 방법도 제시하였다
다음으로 네트워크를 이루는 커뮤니티 구조에 대해 알아보았다.
우리는 널리 사용되고 있는 커뮤니티 찾기 알고리즘에서 발생하는 비일관성 문제를 정량적으로 분석하고 일관성을 유지하는 새로운 커뮤니티 분석 알고리즘을 제안하였다.
다음으로 좀 더 미시적인 구조와 동역학에 주목하였다. 그것은 사회적 관계이다.
싸이월드의 방명록에 기록된 2년 반 이상의 로그를 통해 우리는 방향성이 있고 세기가 있는 행동 네트워크를 만들고 그 특성을 관찰하였었다. 이 두가지 특성은 일반적인 친구 네트워크에서는 볼 수 없는 사회적 관계의 동역학을 보여주었다.
트위터의 팔로우 관계로부터는 사회적 관계의 소멸을 관찰하였다. 백만명 이상의 한국인 유저들의 관계를 51일동안 관찰하고, 유저 스터디를 더하여 우리는 사회적 관계의 소멸에서 볼 수 있는 특성과 동기를 파악하는데 주력하였다.
마지막으로 가장 미시적인 단계에서 온라인 소셜 네트워크를 분석하기 위해 우리는 개인의 특성에 주목하였다. 개인이 사용한 태그들로부터 특정 서비스의 범위를 넘어 비슷한 흥미를 가진 사용자 간의 추천을 통해 개인간의 관계를 형성할 수 있게 한 이 연구는 다양한 서비스로부터 수집한 수백만개의 태그들을 이용해 알고리즘을 제안하고, 유저 스터디를 통해 알고리즘의 성능을 분석하였다.
본 논문은 대량의 데이터를 통해 온라인 소셜 네트워크의 구조와 동역학을 거시적인 시점에서 미시적인 시점으로의 다층적 접근을 통해 분석하였다. 이 연구가 온라인 소셜 네트워크에서 관찰되는 복잡한 현상을 이해하고, 온라인 소셜 네트워크의 분석과 디자인, 운영에 관한 깊은 통찰을 주기를 기대한다.
