Cross-domain community detection in heterogeneous social networks

With the recent surge of location-based social networks (LBSNs), e.g., Foursquare and Facebook Places, huge amount of human digital footprints that people leave in the cyber-physical space become accessible, including users’ profiles, online social connections, and especially the places that they have checked in. Different from social networks (e.g., Flickr, Facebook) which have explicit groups for users to subscribe or join, LBSNs usually have no explicit community structure. Meanwhile, unlike social networks which only contain a single type of social interaction, the coexistence of online/offline social interactions and user/venue attributes in LBSNs makes the community detection problem much more challenging. In order to capitalize on the large number of potential users/venues as well as the huge amount of heterogeneous social interactions, quality community detection approach is needed. In this paper, by exploring the heterogenous digital footprints of LBSNs users in the cyber-physical space, we come out with a novel edge-centric co-clustering framework to discover overlapping communities. By employing inter-mode as well as intra-mode features, the proposed framework is able to group like-minded users from different social perspectives. The efficacy of our approach is validated by intensive empirical evaluations based on the collected Foursquare dataset.     

Community detection for emerging social networks

Many famous online social networks, e.g., Facebook and Twitter, have achieved great success in the last several years. Users in these online social networks can establish various connections via both social links and shared attribute information. Discovering groups of users who are strongly connected internally is defined as the community detection problem. Community detection problem is very important for online social networks and has extensive applications in various social services. Meanwhile, besides these popular social networks, a large number of new social networks offering specific services also spring up in recent years. Community detection can be even more important for new networks as high quality community detection results enable new networks to provide better services, which can help attract more users effectively. In this paper, we will study the community detection problem for new networks, which is formally defined as the “New Network Community Detection” problem. New network community detection problem is very challenging to solve for the reason that information in new networks can be too sparse to calculate effective similarity scores among users, which is crucial in community detection. However, we notice that, nowadays, users usually join multiple social networks simultaneously and those who are involved in a new network may have been using other well-developed social networks for a long time. With full considerations of network difference issues, we propose to propagate useful information from other well-established networks to the new network with efficient information propagation models to overcome the shortage of information problem. An effective and efficient method, Cat (Cold stArT community detector), is proposed in this paper to detect communities for new networks using information from multiple heterogeneous social networks simultaneously. Extensive experiments conducted on real-world heterogeneous online social networks demonstrate that Cat can address the new network community detection problem effectively.     

Finding Diachronic Like‐Minded Users

User communities in social networks are usually identified by considering explicit structural social connections between users. While such communities can reveal important information about their members such as family or friendship ties and geographical proximity, just to name a few, they do not necessarily succeed at pulling like‐minded users that share the same interests together. Therefore, researchers have explored the topical similarity of social content to build like‐minded communities of users. In this article, following the topic‐based approaches, we are interested in identifying communities of users that share similar topical interests with similar temporal behavior. More specifically, we tackle the problem of identifying temporal (diachronic) topic‐based communities, i.e., communities of users who have a similar temporal inclination toward emerging topics. To do so, we utilize multivariate time series analysis to model the contributions of each user toward emerging topics. Further, our modeling is completely agnostic to the underlying topic detection method. We extract topics of interest by employing seminal topic detection methods; one graph‐based and two latent Dirichlet allocation‐based methods. Through our experiments on Twitter data, we demonstrate the effectiveness of our proposed temporal topic‐based community detection method in the context of news recommendation, user prediction, and document timestamp prediction applications, compared with the nontemporal as well as the state‐of‐the‐art temporal approaches.     

Flickr group recommendation with auxiliary information in heterogeneous information networks

Over the past few years, the appropriate utilization of user communities or image groups in social networks (i.e., Flickr or Facebook) has drawn a great deal of attention. In this paper, we are particularly interested in recommending preferred groups to users who may favor according to auxiliary information. In real world, the images captured by mobile equipments explicitly record a lot of contextual information (e.g., locations) about users generating images. Meanwhile, several words are employed to describe the particular theme of each group (e.g., “Dogs for Fun Photos” image group in Flickr), and the words may mention particular entities as well as their belonging categories (e.g., “Animal”). In fact, the group recommendation can be conducted in heterogeneous information networks, where informative cues are in general multi-typed. Motivated by the assumption that the auxiliary information (visual features of images, mobile contextual information and entity-category information of groups in this paper) in heterogeneous information networks will boost the performance of the group recommendation, this paper proposes to combine auxiliary information with implicit user feedback for group recommendation. In general, the group recommendation in this paper is formulated as a non-negative matrix factorization (NMF) method regularized with user–user similarity via visual features and heterogeneous information networks. Experiments show that our proposed approach outperforms other counterpart recommendation approaches.     

一种融合多维信息的移动社区发现方法

为解决传统社区发现算法难适用于大型复杂异质的移动网络的问题,利用移动网络使用详单数据（Usage Detail Record, UDR）和移动用户社交数据构建网络模型,提出一种融合多维信息的移动社区发现方法BNMF-NF。该方法综合考虑用户社交关系和时空行为,给出用户社交相似度、位置分布相似度和主题偏好相似度,利用加权网络融合方法融合多维相似关系构建用户相似网络,并运用有界非负矩阵分解技术实现社区结构的检测。在Foursquare和电信数据集上的实验结果表明,BNMF-NF方法能够有效发现移动网络中用户社区结构。     

Data dissemination using interest-tree in socially aware networking

Socially aware networking (SAN) exploits social characteristics of mobile users to streamline data dissemination protocols in opportunistic environments. Existing protocols in this area utilized various social features such as user interests, social similarity, and community structure to improve the performance of data dissemination. However, the interrelationship between user interests and its impact on the efficiency of data dissemination has not been explored sufficiently. In this paper, we analyze various kinds of relationships between user interests and model them using a layer-based structure in order to form social communities in SAN paradigm. We propose Int-Tree, an Interest-Tree based scheme which uses the relationship between user interests to improve the performance of data dissemination. The core of Int-Tree is the interest-tree, a tree-based community structure that combines two social features, i.e., density of a community and social tie, to support data dissemination. The simulation results show that Int-Tree achieves higher delivery ratio, lower overhead, in comparison to two benchmark protocols, PROPHET and Epidemic routing. In addition, Int-Tree can perform with 1.36 hop counts in average, and tolerable latency in terms of buffer size, time to live (TTL) and simulation duration. Finally, Int-Tree keeps stable performance with various parameters.     

Actively learning to infer social ties

We study the extent to which social ties between people can be inferred in large social network, in particular via active user interactions. In most online social networks, relationships are lack of meaning labels (e.g., ??colleague?? and ??intimate friends??) due to various reasons. Understanding the formation of different types of social relationships can provide us insights into the micro-level dynamics of the social network. In this work, we precisely define the problem of inferring social ties and propose a Partially-Labeled Pairwise Factor Graph Model (PLP-FGM) for learning to infer the type of social relationships. The model formalizes the problem of inferring social ties into a flexible semi-supervised framework. We test the model on three different genres of data sets and demonstrate its effectiveness. We further study how to leverage user interactions to help improve the inferring accuracy. Two active learning algorithms are proposed to actively select relationships to query users for their labels. Experimental results show that with only a few user corrections, the accuracy of inferring social ties can be significantly improved. Finally, to scale the model to handle real large networks, a distributed learning algorithm has been developed.     

Ubiquitous conference management system for mobile recommendation services based on mobilizing social networks: A case study of u-conference

In this paper, we propose a social network-based mechanism to be aware of user contexts and to provide contextually relevant mobile services to users. A social network among users is regarded as the channel for exchanging and propagating their contexts. To efficiently discover the contexts of a certain users the contexts of his neighbors can be fused to provide mobile recommendation service to mobile subscribers. However, since the social network of a user has been fragmented into more than one, it is difficult to put the number of contexts from the fragmented social networks together (Jung, 2009b). Thereby, we mobilize all possible on- and off-line social networks to build an ego-centric social network. We have implemented the proposed system, which is called u-conference system, by collecting the social network dataset from online (e.g., Facebook, Twitter, CyWorld, and co-authoring patterns in major Korean journals) and offline (e.g., co-participation patterns in a number of Korean domestic conferences). Once we have implemented the system, we have provided mobile services to the conference participants by sending text messages about time schedule of relevant presentations.     

Community detection in social networks using user frequent pattern mining

Recently, social networking sites are offering a rich resource of heterogeneous data. The analysis of such data can lead to the discovery of unknown information and relations in these networks. The detection of communities including ‘similar’ nodes is a challenging topic in the analysis of social network data, and it has been widely studied in the social networking community in the context of underlying graph structure. Online social networks, in addition to having graph structures, include effective user information within networks. Using this information leads to enhance quality of community discovery. In this study, a method of community discovery is provided. Besides communication among nodes to improve the quality of the discovered communities, content information is used as well. This is a new approach based on frequent patterns and the actions of users on networks, particularly social networking sites where users carry out their preferred activities. The main contributions of proposed method are twofold: First, based on the interests and activities of users on networks, some small communities of similar users are discovered, and then by using social relations, the discovered communities are extended. The F-measure is used to evaluate the results of two real-world datasets (Blogcatalog and Flickr), demonstrating that the proposed method principals to improve the community detection quality.     

CSD: A multi-user similarity metric for community recommendation in online social networks

Communities are basic components in networks. As a promising social application, community recommendation selects a few items (e.g., movies and books) to recommend to a group of users. It usually achieves higher recommendation precision if the users share more interests; whereas, in plenty of communities (e.g., families, work groups), the users often share few. With billions of communities in online social networks, quickly selecting the communities where the members are similar in interests is a prerequisite for community recommendation. To this end, we propose an easy-to-compute metric, Community Similarity Degree (CSD), to estimate the degree of interest similarity among multiple users in a community. Based on 3460 emulated Facebook communities, we conduct extensive empirical studies to reveal the characteristics of CSD and validate the effectiveness of CSD. In particular, we demonstrate that selecting communities with larger CSD can achieve higher recommendation precision. In addition, we verify the computation efficiency of CSD: it costs less than 1 hour to calculate CSD for over 1 million of communities. Finally, we draw insights about feasible extensions to the definition of CSD, and point out the practical uses of CSD in a variety of applications other than community recommendation.     

Artificial intelligence control for trust-based detection of attackers in 5G social networks

This study introduces a comprehensive framework designed for detecting and mitigating fake and potentially threatening user communities within 5G social networks. Leveraging geo-location data, community trust dynamics, and AI-driven community detection algorithms, this framework aims to pinpoint users posing potential harm. Including an artificial control model facilitates the selection of suitable community detection algorithms, coupled with a trust-based strategy to effectively identify and filter potential attackers. A distinctive feature of this framework lies in its ability to consider attributes that prove challenging for malicious users to emulate, such as the established trust within the community, geographical location, and adaptability to diverse attack scenarios. To validate its efficacy, we illustrate the framework using synthetic social network data, demonstrating its ability to distinguish potential malicious users from trustworthy ones.     

SOMAR: A SOcial Mobile Activity Recommender

A 2010 survey (Nielsen) showed that 22.7% of the time spent on the Internet is on a social network. Moreover, there is an increasing demand to access social networks by mobile phones, i.e., around 30% globally. Social networking has become a reality, and it generates an incredible amount of information that is sometimes difficult for users to process, especially from mobile phones. Several links, activities, and recommendations are proposed by networked friends every hour, which together are nearly impossible to manage. There is a need to filter and make accessible such information to users, which is the motivation behind developing a mobile recommender that exploits social network information. Thus, in this paper, we propose the design and the implementation of a SOcial Mobile Activity Recommender (SOMAR) that can integrate Facebook social network mobile data and sensor data to propose activities to the user (e.g., concert or computer science seminar). The recommendations are completely calculated in situ in the mobile device with an embedded data mining component. We analyze how to compute and update the social graph in case of changes in social relationships or user context. The paper also presents a case study to analyze the performance of the method.     

The ties that bind: Social network principles in online communities

In a Web 2.0 environment, the online community is fundamental to the business model, and participants in the online community are often motivated and rewarded by abstract concepts of social capital. How networks of relationships in online communities are structured has important implications for how social capital may be generated, which is critical to both attract and govern the necessary user base to sustain the site. We examine a popular website, Slashdot, which uses a system by which users can declare relationships with other users, and also has an embedded reputation system to rank users called ‘Karma’. We test the relationship between user's Karma level and the social network structure, measured by structural holes, to evaluate the brokerage and closure theories of social capital development. We find that Slashdot users develop deep networks at lower levels of participation indicating value from closure and that participation intensity helps increase the returns. We conclude with some comments on mechanism design which would exploit these findings to optimize the social networks and potentially increase the opportunities for monetization.     

Remodeling the network for microgroup detection on microblog

In this paper, we focus on the problem of community detection on Sina weibo, the most popular microblogging system in China. By characterizing the structure and content of microgroup (community) on Sina weibo in detail, we observe that different from ordinary social networks, the degree assortativity coefficients are negative on most microgroups. In addition, we find that users from the same microgroup tend to share some common attributes (e.g., followers, tags) and interests extracted from their published posts. Inspired by these new findings, we propose a united method to remodel the network for microgroup detection while maintaining the information of link structure and user content. Firstly, the link direction is concerned by assigning greater weight values to more surprising links, while the content similarity is measured by the Jaccard coefficient of common features and interest similarity based on Latent Dirichlet Allocation model. Then, both link direction and content similarity between two users are uniformly converted to the edge weight of a new remodeled network, which is undirected and weighted. Finally, multiple frequently used community detection algorithms that support weighted networks could be employed. Extensive experiments on real-world social networks show that both link structure and user content play almost equally important roles in microgroup detection on Sina weibo. Our method outperforms the traditional methods with average accuracy improvement up to 39 %, and the number of unrecognized users decreased by about 75 %.     

基于自适应差异化图卷积的社交网络新增恶意用户检测

社交网络新增恶意用户检测作为一项分类任务,一直面临着数据样本不足、恶意用户标注稀少的问题。在数据有限的情况下,为了能够精确地检测出恶意用户,提出一种基于自适应差异化图卷积网络的检测方法。该方法通过提取社交网络中的用户特征和社交关系构建社交网络图。构建社交网络图后,计算节点与邻居的相似度,并对邻居进行优先级排序,利用优先级顺序采样关键邻居。关键邻居的特征通过自适应权重的加权平均方式聚合到节点自身,以此更新节点特征。特征更新后的节点通过特征降维和归一化计算得到恶意值,利用恶意值判断用户的恶意性。实验表明该方法和其他方法相比,具有更高的恶意用户查全率和整体查准率,并且能够快速地完成对新增用户的检测,证明了自适应差异化图卷积网络能够有效捕捉到少量样本的关键特征。     

Discovery of Web user communities and their role in personalization

One of the major innovations in personalization in the last 20?years was the injection of social knowledge into the model of the user. The user is not considered an isolated individual any more, but a member of one or more communities. User communities have been facilitated by the striking advancements of electronic communications and in particular the penetration of the Web into people??s everyday routine. Communities arise in a number of different ways. Social networking tools typically allow users to proactively connect to each other. Alternatively, data mining tools discover communities of connected Web sites or communities of Web users. In this article, we focus on the latter type of community, which is commonly mined from logs of users?? activity on the Web. We recall how this process has been used to model the users?? interests and personalize Web applications. Collaborative filtering and recommendation are the most widely used forms of community-driven personalization. However, we examine a range of other interesting alternatives that are worth investigating further. This effort leads us naturally to the recent developments on the Web and particularly the advent of the social Web. We explain how this development draws together the different viewpoints on Web communities and introduces new opportunities for community-based personalization. In particular, we propose the concept of active user community and show how this relates to recent efforts on mining social networks and social media.     

Towards understanding the gamification upon users’ scores in a location-based social network

Online social platform, such as Wikipedia and Foursquare, has been increasingly exploded due to not only various useful services provided but also social gaming mechanisms that can keep users actively engaged. For example, users are awarded ”virtual goods” like badges and points when they contribute to the community in the network by voluntarily sharing ideas and other information. In this paper, we aim to examine the effectiveness of a social gamification mechanism, named user scores, designed in Foursquare which is one of most popular location-based social networks. A user’s score in Foursquare is an aggregate measure based on recent check-in activities of the user, which reflects a snapshot summary of the user’s temporal and spatial behaviors. Whenever a user checks in to a venue, a list of scores of the user’s friends are visible to the user via a ”leaderboard” which ranks these users’ scores in a descending order. Given a pair of friends who participate in a score competition in such a gimification mechanism, we identify if one user’s scores have significant influence on the other user’s scores by utilizing the Granger Causality Test. To understand what types of users and what types of friends tend to participate in the score competition (i.e., their check-ins are more likely driven by such a gamification mechanism), we extract users’ features (e.g. user’s degree) as well as the features of pairs of friends (e.g., number of common friends, score similarity and ranking difference) to examine whether these features have correlations with those pairs of users who are identified as being involved in the score game. The identified influence on user scores has the important implication on applications including friend and venue recommendations in location-based social networks.     

Communities on the road: fast triggering of interactive multimedia services

Social network communities are involving millions of users, representing one of the main reasons why people log on the Internet from their home computers. Part of this success is certainly due to the possibility for end users to reverse the traditional publisher/consumer model, achieving control over service consumption, and gaining the opportunity to produce multimedia contents instantaneously available worldwide. Social network communities are not destined to be confined in traditional wired networks. Indeed, mobile users could greatly benefit from applications that combine social networks and location-based multimedia services. It is hence of particular interest to consider the next frontier in wireless networking, i.e., vehicular networks, and imagine how community-based services could be provided in this highly variable context, enabling the sprouting of communities on the road. To this aim, we address here one of the specific challenges in this scenario, i.e., the fast delivery of service triggering messages generated by a user to a certain area where another user can provide the requested multimedia service (e.g., live video streaming, traffic updates, friends finder, status messages of social network applications). We discuss the state-of-art for this technical challenge and compare it against our solution, which is able to dynamically adapt to different transmission conditions as those featuring a vehicular network. In essence, the main innovation of our contribution amounts to a transmission range estimator that enables vehicles to know their current transmission range, independently from changes in the vehicular network topology, and use it to maximize the efficiency in transmitting service-triggering messages.

基于ICN网络架构的社区感知型MSN路由机制

移动社交网络（mobile social network，简称MSN）利用移动用户之间的社交关系，通过节点间的协作式转发实现消息交付.然而，随着大数据时代的到来，MSN需要满足移动用户日益增长的对内容（如视频）的需求.由于信息中心网络（information-centric networking，简称ICN）对移动性的支持，基于ICN架构，提出了一种MSN中基于社区划分的路由机制.在兴趣决策中，利用节点请求中的内容名字获取用户的兴趣偏好，进而计算用户间的兴趣差异度量；根据兴趣差异将节点划分为兴趣社区，依据这些兴趣社区进行兴趣包路由.在数据决策中，根据节点历史相遇信息计算用户间的相遇规律度量，根据相遇规律将节点划分为社交社区，依据这些社交社区进行数据包路由.同时，根据兴趣社区和社交社区信息优化节点的内容缓存，以快速满足未来的内容请求.进行了仿真实验，通过与现有机制在包交付率、平均延迟、平均跳数和网络开销方面的性能对比，表明所提出的机制是可行且有效的.     

移动社交网中基于兴趣社区的消息传输方案

节点对路由消息的存储-携带-转发是移动社交网中的一种短距离通讯方式,传输性能是影响用户交互体验的关键因素,如果用户能够根据彼此间的兴趣或社区来进行消息传输,则可提高传输性能。目前,针对移动社交网中的短距离通讯,已有的研究主要是基于兴趣或者基于社区的传输方式。为了使用户得到更好的交互体验,将用户兴趣与社区相结合,提出基于兴趣社区的消息传输方案InComT(Interest Community based Transmission)。对移动社交网中单个节点的兴趣进行度量,根据得出的节点兴趣值进行社区划分,从而确定社区整体的兴趣值,并根据兴趣值来选择中继社区和中继节点,实现消息的传输。仿真结果表明,该策略在传输负载率和平均延时较低的情况下能够拥有较高的传输成功率。