•   Quick Search:       Advanced Search
    XU Yunfeng,ZHAO Ning,HAO Xuejun,LI Bing,LIU Huijuan.A community detection algorithm based on triadic closure and membership closure[J].Journal of Hebei University of Science and Technology,2014,35(1):103-108
    A community detection algorithm based on triadic closure and membership closure
    Received:November 01, 2013  Revised:December 02, 2013
    中文關鍵詞:  社交網絡  三元閉包  社區劃分
    英文關鍵詞:social network  number of triadic closure  community divide
    Author NameAffiliation
    XU Yunfeng School of Information Science and Engineering, Hebei University of Science and Technology 
    ZHAO Ning Personnel Department, Hebei University of Science and Technology 
    HAO Xuejun School of Information Science and Engineering, Hebei University of Science and Technology 
    LI Bing School of Information Science and Engineering, Hebei University of Science and Technology 
    LIU Huijuan School of Information Science and Engineering, Hebei University of Science and Technology 
    Hits: 8304
    Download times: 3216
          隨著網絡的發展和人們溝通方式的擴展,社交網絡影響了人們的生活,改變了人們傳播與分享消息的方式,吸引了越來越多的人關注和研究社交網絡。社交網絡即社交網絡服務,源自英文SNS(social network service)的翻譯,社交網絡有多種表現平臺,比如QQ、微博、Facebook和微信。本文主要研究微博這一新興的社交平臺,研究微博的主要目的是搞清用戶之間的種種關系。當代人一般認為,微博中存在5種關系即關注關系、提及關系、轉發關系、評論關系以及好友關系。由于社交網絡中人數眾多,關系錯綜復雜,因而產生的社交數據和傳統的數據相比具有數據量大、結構復雜、語義豐富等特點,針對這種情況,依據用戶之間的關系,提出了一種基于三元閉包的社區劃分算法。該算法首先設初始社區為空,在所有的頂點中,選擇度最大的頂點作為初始頂點;然后求初始頂點與其鄰接頂點的三元閉包數和頂點屬于該社區的概率PS,取它們最大的鄰接頂點加入初始頂點所在社區,形成新的社區,繼續迭代,當剩余的頂點很少時,可以使用會員閉包和三元閉包這種歸集算法把剩余的頂點劃分到不同的社區,直到把整個社區劃分完畢;最后以圖形這種直觀、形象的方式把每一個社區表示出來。在該算法中,三元閉包數、頂點屬于某社區的概率、擴張度的差是評估復雜網絡中頂點劃分的關鍵。該方法綜合了頂點全局重要性的特點,即在復雜網絡中,三元閉包數越大,它們處在一個社區的可能性就越大;頂點的會員閉包越大,該頂點就會越優先被劃分;擴張度的差是確定第i個社區是否被劃分完畢的關鍵。社交網絡的研究不僅可以幫助人們了解網絡結構、分析網絡結構特性、探測分析網絡的社團結構,而且還可以把虛擬世界中這種關系鏈接到現實世界中,即把虛擬關系轉化成利潤,為企業提供有價值的關系網絡,從而挖掘出潛藏在社交網絡背后的巨大的經濟價值,具體體現在:1)幫助企業找到潛在的商機,比如分析某個用戶的評論和發表內容,可知他的消費能力、喜好和最近的購買習慣,從而知道他購買自己產品的概率;2)危機預警,根據用戶的消息內容可以知道他對自己產品的滿意度;3)帶動了消息的傳播速度和廣度。企業可以利用這一點,為自己的產品更好地做宣傳。通過與寬吻海豚網和Zachary空手道俱樂部的社區網絡作比較,證明了該算法的有效性和可行性。
          With the development of network and the expansion of people's communication ways, the social network penetrates into almost every corner of the entire society, and changes the ways of information communicating and news sharing, attracting more and more people's attention and research on it. Social network, also named social networking service, originated from the translation of British SNS(social network service), was literally translated as social network services or social networking service in Chinese. There're many manifestations of social networking platforms, such as: QQ, WeChat, Facebook and Micro-blog. In this paper, we mainly focus on the micro- blog, the emerging social platform. The main purpose of research on micro-blog is to find out the various relationships between users. People generally believe there're mainly 5 relations existing in miro-blog among users: the relationship of concerning, mentioning, forwarding, commenting and being friends. Due to the large number of social network users and the complicated relations among them, the generated social data, compared with the traditional data, has the characteristics of large amount of data, complex structure and semantically rich features. So according to the relationship among users, this paper proposes divided community algorithm based on triadic closure. In the first instance, this algorithm took the initial community as being empty, in which the vertex degree maximum among all vertices was chosen as the initial vertex, then requesting for the number of Triadic closures between the initial vertex and the adjacent vertex, and requesting for the probability of vertices belonged to the community. The vertex with the maximum Ps joined the initial vertex community, forming a new initial community. With continued iterating, and by using collection algorithm of triadic and membership closure, the remained few vertices could be divided into different communities until the entire community was completely divided. Finally, every community was intuitively and visually presented by Graphics. When using this algorithm, the number of Triadic closure, the probability of vertex belonged to a community and the difference in expansion degree are the keys to value vertices in complex network. This method combines the characteristics of the global importance of vertices. Namely, in complex networks, the greater the number of Triadic closure is, the greater the likelihood of them in a community will be. The greater the vertex membership closures are, the priorer the vertex will be divided. The difference in expansion degree is to determine whether the i community is divided completely or not. The research of social networking can not only help us understand and analyze the network structure, and detect to analyze network, but also can help link the relationship in virtual world to the real world. So the virtual relationship could be transferred into profits, providing valuable network for enterprises, and digging out the great economic value behind the social network. It can be embodied like this: firstly, to help companies find potential business opportunities by analyzing users' comments and published content to learn their consumption power, preferences and recent buying habits, thus to know the probability that he could purchase products. Second, it can give crisis warning message. According to user's information, products satisfaction degree of users can be learnt. Third, it can drive the information propagation speed and message breadth, of which the enterprises take advantage, achieving better product publicity. Compared with the community network of Bottlenose Dolphin Internet and Zachary, the algorithm mentioned in this paper was proved to be effective and feasible.
    View Full Text  View/Add Comment  Download reader