Li, D., He, B., Ding, Y., Tang, J., Sugimoto, C., Qin, Z., ... & Dong, T. (2010, October). Community-based topic modeling for social tagging. In Proceedings of the 19th ACM international conference on Information and knowledge management (pp. 1565-1568). ACM.

Li, D., He, B., Ding, Y., Tang, J., Sugimoto, C., Qin, Z., ... & Dong, T. (2010, October). Community-based topic modeling for social tagging. In Proceedings of the 19th ACM international conference on Information and knowledge management (pp. 1565-1568). ACM.

本研究提出一個TTR-LDA-社群模型，這個模型以推論機制(inference mechanism)結合LDA(Latent Dirichlet Allocation)模型和Girvan-Newman社群偵測(community detection)演算法提供在網路資料上偵測社群並對這些社群進行主題探勘(topic mining)的功能，並且進而了解在社群上的主題隨時間推移的變化，處理的架構如下圖所示

本研究利用Delicious社會標籤系統(social tagging system)上從2005到2008年的資料進行研究。在社群偵測部分，首先建立網絡：根據使用者標籤的資源數量，選取前50000位標籤資源最多的使用者；然後對他們標籤的網頁進行統計，從其中選取10000個被最多使用者標籤的網頁。接著在上述的10000個網頁中，如果有這50000位使用者之間有任何兩位曾經標籤過相同的網頁，便在這兩位使用者之間產生一個連結。以50000個使用者為節點，同時以他們之間的連結為連結線，便可以建立一個共同書籤網絡(co-bookmark network)。並且為了研究網絡上社群結構的變化，並將整個期間的資料分為三個時段：分別為2005-2006、2007與2008年，相關的統計數據如下表：

本研究利用Girvan-Newman演算法找出標籤者(Tagger)社群，使得標籤者與同一社群內的其他標籤者比社群外的標籤者有較強的關係。這個演算法重複移去當時網絡上中介性(betweenness)最大的連結線，產生各種可能的網路劃分(network partition)，測量每一種劃分下的群組性(modularity)，也就是實際上社群內的成員彼此間的連結線數量與相同連結度的情況但隨機產生連結線的數量的差，群組性最大的劃分便是輸出結果。

另一方面，本研究利用TTR-LDA模型找出每個標籤者的主題分布以及主題內具有代表性的標籤，TTR-LDA模型修改自ACT(author-conference-topic)模式[11][12]，是一個由標籤者做為第一層、標籤與資源為第三層、主題則為第二層，所構成的三層貝氏模型(three-layer Bayesian model)。

整合Girvan-Newman演算法和TTR-LDA模型的方法是以社群為單位，將社群內所有標籤者的主題分布進行平均做為該社群的主題分布，根據主題分布，選出機率值較大的主題做為社群的代表。比較不同時段社群共同的代表標籤衡量它們的相似性。

社群偵測的結果發現前五個最大的社群在四年裡占了絕大多數的比率，而且這個比率逐年增加。主題探勘的部分則測量TTR-LDA模型在不同主題數量上的複雜度(perplexity)，發現150個主題時有最低的複雜度。因此，以下的研究便針對150個主題在前五個最大社群上的分布進行探討，計算它們的傳導性(conductance)與模組性。就社群模組性而言，最近一個時段(2008年)的結果比前三個時段還要高，其原因可能是因為經過一段時間後，社群的結構逐漸成熟，因此後期比前期更能產生較佳的社群。另外，將最後一個時段再細分為四個較小的時段則發現，較小時段的社群模組性比整年的結果來得高，本研究認為造成這種現象的原因可能是由於在不同的時段，大部分標籤者的書籤行為集中在不同的領域；當那些時段合併起來的時候，會展現標籤者在多個領域的興趣，使得社群內的叢集(clustering)特性較弱。

結果並可以發現前二十個主題都出現在不同時段的前五個最大社群裡，每個社群至少包括一個前十名的主題。此外，比較LDA、TTR-LDA和TTR-LDA-社群等三種模型在資源和標籤上的預測力，在回收率(recall rate)、精確率(precision)和F1指標上以TTR-LDA-社群為最佳。

In this paper, we propose a TTR-LDA-Community model which combines the Latent Dirichlet Allocation model (LDA) and the Girvan-Newman community detection algorithm with an inference mechanism.

The model is then applied to data from Delicious, a popular social tagging system, over the time period of 2005-2008.

Our results show that 1) users in the same community tend to be interested in similar set of topics in all time periods; and 2) topics may divide into several sub-topics and scatter into different communities over time.

From a research perspective, these real-world networks display unique properties from the classical random graph model [3] in that most real word networks exhibit three common properties: the small-world property, power-law degree distribution and a high clustering coefficient or transitivity (indicating community structure) [7][8][9].

Thus, an important task in network analysis is to detect communities and explore their features, which can improve community-supporting services at the community-level in the context of a social tagging system.

Many studies in various disciplines have been devoted to community detection; however, few of them have systematically and quantitatively studied the profiles of those detected communities.

In this paper, we propose a TTR-LDA-Community model, which is an inferential combination of an extended LDA model and a betweenness-based community detection algorithm. It provides rich, systematic, and quantitative information about the profiles of detected communities.

In the context of social tagging systems, where multiple users are annotating resources, the resulting topics reflect a shared view of the document; and the tags of the topics reflect a common vocabulary.

Girvan and Newman extended the betweenness measure to edges and designed a clustering algorithm which gradually removes the edges with the highest betweenness value [4]. This algorithm has been improved through modularity; and the complexity is reduced from O(m²n) to O(mdlogn) where d is the depth of the dendrogram of the community structure [2].

Many studies provide various models and algorithms for topic mining and community detection; yet, few of them have integrated those models and algorithms, performed topic mining for detected communities, and analyzed how those identified topics change among communities over time.

The activity of social tagging consists of three major components: tag, tagger and resource. The experimental dataset contains all the triples of these three components and the time and date of their creation on Delicious from 2005 to 2008.

In data processing, all taggers were ranked by the number of resources they have bookmarked and the top 50,000 taggers were selected as the sample of taggers.

These taggers bookmarked a total of 354,522 web pages, which were sorted by the number of taggers who bookmarked them. The top 10,000 resources were selected as the sample of web pages, associated with which a dominant majority of tagging activities occurred.

Thus a co-bookmark network was built in which a connection between two users (within the sample of 50,000 taggers) is created if they bookmarked the same resources (within the sample of 10,000 web pages).

In addition, in order to observe the evolution of structure and motif of communities, the time span (2005-2008) was divided into three slices.


The model is illustrated in Figure 1. TTR-LDA is developed based on ACT model [11][12]. It is a three-layer Bayesian model with taggers tap in each post p as the first layer, tags t, and resource r as third layer and all the topics denoted as latent variable z as the middle layer.

The inference mechanism is used to infer the topic distribution over detected communities.

Each community includes a set of taggers, who have a stronger relationship with other taggers within the community than the taggers outside.

Based on the taggers’ information model, the probability distribution of each tagger over a set of topics is obtained by using the TTR-LDA model while the community structure of taggers is revealed by the community detection algorithm. The two sets of results are further integrated through an inference mechanism.




Results show that the number of users of the top five communities occupies a major proportion in the four years (2005-2008) and the proportion is increasing over time.

Perplexity is used to identify the number of topics [10], which arrives at the lowest point when the number of topics is 150. The interest model of each tagger in the top five largest communities is then built based on their topic distributions.

By using users’ interest models and the inference mechanism, a topic distribution of the largest community can be created (Figure 3). We can find that the topic distributions in a community are diverse because users’ relationships in that community are mainly based on their co-bookmark activities not the similarity of their interest model.

In order to observe the dynamic features of communities, we design an experiment as follows:
1) denote the five largest communities from each time slice in 2008 as community_i_t where t means the tth time slice in 2008 and i means the ith largest community in tth time slice;
2) compute the topic distribution for the five communities, which is stored as model_t_i_Topic(j), the
probability of jth topic in ith largest community in the tth time slice;
3) obtain the probability distribution of tags that are collected from all the posts generated during the specific time slice; the probability of one tag occurring in a topic shows the level of representativeness of the tag for that topic;
4) sort all the tags according to their probability value in each topic and select the 20 top ranked tags to represent the content of the topics; select the top 5 ranked topics to represent the theme of each community;
5) analyze the similarity between different communities from different time slice through computing how many tags are shared by the two different communities. More specifically, we compare current time slice with its previous time slice, for example, we compare community_i_t with community_j_t-1 (j=1, 2…5).

The size of communities along evolutionary lines fluctuates over time. For example, the size of the community about social networks in the 3rd time slice (community_1_3) is much larger (4,377) than that (521) in the 4th time slice (community_5_4).

Conductance (from multi-criterion scores) and modularity (from single criterion scores) are used to evaluate the quality of communities detected by the TTR-LDA-Community model [6].

The smaller the value of conductance is, the higher the granularity of a community is. Network community profile (NCP) is used to compute and display the value of conductance for communities [5].

Whiskers networks and rewired networks are adopted as two comparative aspects. Whiskers is defined as the maximal sub graphs that can be detached from the rest of the network by removing a single edge; and a rewired network is a random network that has the same nodes and the same degree distribution as the original network [5].

The conductance of communities of the rewired original network (blue line in the left figure), rewired random network (red dashed line in the left figure), the original whiskers network (blue line in the right figure), and the random whiskers network (red dashed line in the right figure) are calculated and shown in Figure 4.

In Figure 4, compared with the rewired network (left) and the rewired whiskers (right), 1) the original network displays a higher granularity of communities (a lower conductance value); 2) the value of conductance as the function of the size of communities in the original network and the original whiskers present a “V” shape, showing properties of a true large social networks [5]; 3) the original whiskers has the best community granularity (the lowest conductance) between size 10-100; and 4) the best community granularity of rewired original network is around 1000.

The modularity of communities in the four time slices of 2008 is better than that in 2005-2007. This is probably due to the fact that community structure grows mature gradually over time, creating better communities in later years than in earlier years.

Meanwhile, modularity of communities in the short-term (four sub periods in 2008) is larger than the long-term (2008). It can be explained that in different time periods, most taggers’ bookmarking activities are focused on different domains, so in a certain short-term time period, communities may be quite different from each other. However, when those time periods are merged together, the taggers show different interests in many domains; so the clustering feature within the communities becomes weaker.

Results show that the most popular topics are about bandslash fiction, fan fiction, and supernatural fiction (the top 3 popular topics). Communities with similar theme are ranked 3rd, 4th, and 5th in size; and the web resources with similar topics are ranked 500-600 of the top 1000 ranked resources in number of taggers associated with them.

The top 20 ranked topics in 1000 most popular resources can be found in 5 largest communities in different time periods. For each community, there exists at least one topic that is ranked top 10 in 1000 most popular resources (Table 3).

Topic distributions for each community are obtained respectively from LDA, TTR-LDA model, and TTR-LDACommunity model based on co-bookmark network in a given period (Oct. 2008–Dec. 2008). One resource and five tags are recommended for each post according to the results of three models separately.

The TTR-LDA and TTR-LDA-Community model show significant improvement for recommendation of tags and resources for post in terms of precision, recall and F1-Measure. TTR-LDA and TTR-LDA-Community have slightly improved performance for “tags for post”, while TTR-LDA-Community outperforms TTR-LDA on “resource for post”.

Cha, Y., & Cho, J. (2012, August). Social-network analysis using topic models. In Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval (pp. 565-574). ACM.

Topic Model & LDA

本研究建議運用LDA(latent Dirichlet allocation)模型對社交網絡上圖式資料(graph)的節點與連結線進行分群(grouping)以及標示(labeling)，藉以改善K-means [15] 及 DBSCAN [6]等常用方法無法對節點進行多重分群或是無法同時標註節點與連結線等問題。

過去在社交網絡上應用LDA模型的研究大多是根據作者-主題模型(author-topic model, AT model)[22]修改發展而來，著名的研究包括社群使用者主題(community user topic, CUT)模型[27]、作者-接收者-主題(author-recipient-topic, ART)模型與角色-作者-接收者-主題(role-author-recipient-topic, RART)模型[16]以及社群-作者-接收者-主題(community-author-recipient-topic, CART)模型[19]。此外，Zhang et al. [26]和Henderson et al. [9]的研究都是將LDA模型應用於學術社交網絡(academic social networks)，Zhang et al. [26]的研究目的是探討將合著資訊(co-authorship)轉換為圖式資料的方法，Henderson et al. [9]的重點則是在處理圖式資料中大量的較低連結的節點。

圖式資料的分群問題如下圖所表示，F與G分別是連結線開頭與結尾的節點所成的集合，E則是連結兩邊節點的連結線所成的集合，Z代表的是連結線的標示以及節點的分群。這個研究要探討的問題是如何標示F與G的節點之間的連結線？並且如何根據連結線的標示結果將G內的節點分群？

如果某一節點f_i連結到另一個節點g_j，是因為f_i對g_j中的某一個主題有共同的興趣。一個人可能會對多個主題感興趣，因此節點f_i會連結到會來自不同主題的節點，就如同文件中會包含不同主題的詞語一樣，並且這些主題的分布為多元常態分布(multinormal distribution)。同樣的情形，每一個被連結到的節點可以出現在多個不同的主題上。另一方面，許多人會對某個特定主題有不同程度的興趣，因此每個主題內包含的節點也呈現多元常態分布，就像主題可以利用多種不同的詞語來表示，並且有些詞語會比其他的詞語相關。因此圖式資料的分群與標示問題可以將F與G內的節點分別類比成文件以及文件上出現的詞語，並且應用LDA模式的概念，利用得到的隱藏主題做為連結線的標示，並且對G內的節點的節點分群。

但是由於LDA本身是基於文件生成而發展的模型，在這個模型裡，出現在過多文件上的詞語通常比較無法代表特定的主題，被認為較不重要的詞語，因此往往會預先被過濾，不參與模型的訓練；然而在諸如社交網絡的圖式資料連結許多節點的節點則往往能夠代表多個較重要的主題，因此在將LDA模型應用於圖式資料的節點與連結線分群及標示應用時，應該納入這些連結較多的節點進行分析。本研究改良了LDA模型來解決上述的問題，使其可以運用於社交網絡平台上的朋友推薦(friend recommendations)功能。

本研究提出四種改良方案：
1) 以不對稱的先驗機率(a prior)取代對稱的先驗機率(a prior)，使得連結較多的節點具有較高的先驗機率，例如使用下面的式子做為先驗機率的估計值。


2) 利用階層式LDA(hierarchical LDA)模型，使得較常出現的主題在上層，比較特定的主題則在下層。

3) 採用兩階段標示(two-step labeling)方式，第一階段先排除連結較多的節點以及連結到這些節點的連結線，只利用連結較少的節點資料建立主題，避免連結較多的節點的干擾，第二階段則利用第一階段建立好的主題，以下面的公式對連結較多的節點的連結線進行標示。

此處P(e(f, g) = z|. )為將從 f 到g的連結線標示為某一個主題z的機率，N_gz和N_fz分別表示g和f被標示為z的次數。

4)對每一個節點設定如下面公式中的閾值(threshold)，當節點被標示為某一主題的次數超過此一閾值時才採入計算，讓連結數量較多的節點可以僅指定幾個較有可能的主題。另一種方式則是節點被標示為某一主題的次數只採計前面幾個次數較多的主題，其餘的主題均不納入計算。


本研究從2009年十月到2010年一月間2億7千三百萬餘筆的Twitter資料中選取1千萬筆資料進行實驗，標示的主題個數為100，研究結果發現不管是複雜度(perplexity)或是分群的品質，後兩種方法(兩階段標示以及雜訊閾值過濾)都比其他的方法有較好的成效。

In this paper, we discuss how we can extend probabilistic topic models to analyze the relationship graph of popular social-network data, so that we can "group" or "label" the edges and nodes in the graph based on their topic similarity.

In particular, we first apply the well-known Latent Dirichlet Allocation (LDA) model and its existing variants to the graph-labeling task and argue that the existing models do not handle popular nodes (nodes with many incoming edges) in the graph very well. We then propose possible extensions to this model to deal with popular nodes.

Our proposed methods can be used for providing, for instance, more relevant friend recommendations within a social network.

In this paper, we explore techniques to provide more structure to this follow relationship (1) by "grouping" the users based on their topic interests, and (2) by "labeling" each follow relationship with the identified topic group.

Roughly, we can consider our goal as a clustering (or classification) problem, where many popular solutions such as K-means [15] and DBSCAN [6] exist. These existing methods, however, are not appropriate for our task because they either (1) associate each node with a single group (hard clustering) or (2) can associate each node with multiple groups (soft clustering), but require a completely separate method to label edges as well as nodes (since a node may be associated with multiple groups).

In this paper, we apply a well-known probabilistic topic model, called Latent Dirichlet Allocation (LDA), to the follow relationship graph of the social network, in order to label the nodes and the edges in the graph with (possibly) multiple topics. ...In particular, the direct application of LDA to our task requires that every node in the graph should be of roughly equal popularity and that we should remove nodes of high popularity from the dataset. This is particularly problematic because these popular nodes are really the ones that we want to label accurately; many users are particularly interested in identifying the topic groups of these popular users. Earlier work on the application of the LDA model to social graph [9, 26] has not addressed the handling of popular nodes.

Recently, Mislove et al. [18] identified communities in Facebook based on the social graph structure and inferred unknown attributes through this community information. The methods they used to cluster communities are based on pruning edges from the whole social graph and adding edges from some seed nodes, both of which are very common and widely used approaches in social-network analysis. However, these approaches produce mutually exclusive groups and cannot support multiple memberships, which is important in our scenario where users have a variety of interests.

Though not directly related to social-network analysis, the concept of author/user was initially introduced in the Author-Topic (AT) model [22]. It was used to extract hidden research topics and trends from CiteSeer's abstract corpus.

Zhou et al. [27] modified the AT model and proposed the Community User Topic (CUT) model to capture semantic communities.

McCallum et al. [16] extended the AT model and proposed the Author-Recipient-Topic (ART) model and the Role-Author-Recipient-Topic (RART) model in order to analyze the Enron e-mail corpus and an academic e-mail network.

Pathak et al. [19] modified the ART model and suggested the Community-Author-Recipient-Topic (CART) model similar to the RART model.

Besides these members of the AT model family, Wang et al. [24] introduced the Group Topic (GT) model and applied it to voting data from US Senate and the General Assembly of the UN.

Mei et al. [17] also introduced a regularized topic modeling framework incorporating a graph structure in the data.

Other LDA extensions and probabilistic topic models were also proposed for annotation data analysis [12], chat data analysis [23], tagging data analysis [8], and pairwise data analysis [2].

Perhaps the work by Zhang et al. [26] and by Henderson et al. [9] is closest to our work. In both works, the authors applied LDA to academic social networks. However, their respective focus was quite different from ours.

For example, [26] focused on the issue of how to convert the co-authorship information into a graph (e.g., direct co-authorship or indirect co-authorship, and edge weighting scheme based on collaboration frequency).

Henderson et al. [9] addressed the issue of a large number of topic clusters generated due to low popularity nodes in the network, while our primary focus is the effective clustering of high popularity nodes.

Because LDA evolved from Probabilistic Latent Semantic Indexing (PLSI) [11], we rst describe the concept of PLSI and then explain what di erentiates LDA from PLSI. ... PLSI introduced a probabilistic generative model to topic models. Equation (1) represents its document generation process based on the probabilistic generative model:

P(d, w) is the probability of observing a word w in a document d and can be decomposed into the multiplication of P(d), the probability distribution of documents, and P(w|d), the probability distribution of words given a document. This equation describes a word selection for a document, where we first select a document then a word in that document. If we iterate this selection multiple times, we can generate a document and eventually a whole document corpus.

By assuming that there is a latent topic z, we can rewrite the equation above with the multiplication of P(w|z), the probability distribution of words given a topic, and P(z|d), the probability distribution of topics given a document. This equation describes adding an additional topic selection step between the document selection step and the word selection step. As there are multiple latent topics where a word may come from, we sum the multiplication over a set of all the independent topics Z.

Though PLSI is equipped with a sound probabilistic generative model and a statistical inference method, it suffers from the overfitting problem and does not cope well with unobserved words.

To solve this problem, Blei et al. [4] introduced Dirichlet priors α and β to PLSI, to constrain P(z|d) and P(w|z), respectively.

α is a vector of dimension |Z|, the number of topics, and each element in α is a prior for a corresponding element in P(z|d). Thus, a higher α_i implies that the topic z_i appears more frequently than other topics in a corpus.

Similarly, β is a vector of dimension |W|, the number of words, and each element in β is a prior for a corresponding element in P(w|z). Thus, a higher β_j implies that the word w_j appears more frequently than other words in the corpus.

As a conjugate prior for the multinomial distribution, the Dirichlet distribution can also simplify the statistical inference. By placing Dirichlet priors α and β on the multinomial distributions P(z|d) and P(w|z), those multinomial distributions are smoothed by the amount of α and β and become safe from the overfitting problem of PLSI.

Thus, we use the term follow when a user adds another user as her friend. Formally, when a user f follows a user g, f generates a follow edge, or simply an edge, e(f; g) from a follower f to a followed user g. We also use e'(f; g) to denote an edge from g to f (indicating that g is followed by f), e(f) to denote the set of all outgoing edges from f, and e'(g) to denote the set of all incoming edges to g. To
refer to the set of all followers, the set of all followed users, and the set of all edges in the dataset we use F, G, and E, respectively.

Figure 1(a) depicts this notation using a graph that we refer to as a subscription graph. ... Given this subscription graph, our goal is to label each edge with a correct label (interest) and group (label) each followed user based on those labeled edges. Now we can frame our problem as the graph labeling problem of automatically associating each user g_i in G with a set of accurate interests z_k in Z based on its labeled incoming edges e'(g_i). (We also label f_j in F as well.)

Furthermore, we can consider a follower f to be a document d, a followed user g as a word w, and a list of followed users for the follower as the content of the document.

However, there is a subtle difference between the two generative processes. While words are sampled with replacement in the standard LDA, followed users are sampled without replacement in our model. For example, in a document generative model, a document may contain the word car multiple times. On the other hand, in our edge generative model, a user cannot follow the same user Barack Obama multiple times. As a result, the probabilistic distribution in our model does not follow a multinomial distribution but follows a multivariate hypergeometric distribution. Fortunately, the multinomial distribution can also be used for our model because it is known that a multivariate hypergeometric distribution converges to a multinomial distribution as the sample size grows large [1]. In our case, since sampling is done on millions of nodes, the two distributions become practically indistinguishable.

Also, when we represent E in matrix form by putting F in the rows and G in the columns as E (belongs) power(B, FXG), where B = {0,1}, some differing aspects are noticed:

As in a matrix formed from a document corpus, the distribution of the column sums show a power-law distribution, in which some small portion of the columns accounts for a majority of the total column document corpus, these columns correspond to words such as the and is, which we call stop words, and are generally removed. Those columns in our matrix, however, correspond to users such as Barack Obama and Britney Spears, which we can call popular users, and should be taken into account.

In a document corpus analysis, the stop words are generally removed before analysis, since an analysis without removing these stop words produces a very noisy result where the frequent stop words are labeled with every topic [4]. However, in our analysis, popular users are very important to include in the analysis because most users are keenly interested in following famous and influential users whose topic interests are similar to theirs. Unfortunately, it is not sufficient to simply include the popular users for LDA analysis, because the inclusion of popular users produces the same noisy result seen in the text analysis case: when stop words (or popular users) are included, they get included in every topic group, producing a very noisy result.

Though each element of vectors α and β may take different values in principle, in the standard LDA, each element of α and β is assumed to have the same value (often referred to as the symmetric prior assumption). Intuitively, this assumption implies that every topic and word in a document corpus is equally likely. ... As a higher prior value implies a higher likelihood of being observed in the corpus, we set each prior value proportional to the number of incoming edges of each followed user. It is expected to associate popular users with more accurate labels as they are given adequate prior values.
We set β_gi , the prior for the followed user g_i in the vector , as in Equation (3):

Hierarchical LDA (HLDA) is also a good candidate for our problem because it generates a topic hierarchy and more frequent topics are located at higher levels.

In HLDA, when a document is generated according to Equation (1), words are chosen from topics in a document path. Since the top level topic is associated with all the documents, common words in every document (i.e., stop words) are expected to be labeled with the top level topic. On the contrary, the bottom level topics are expected to be more specific as they are associated with a small number of documents.

This topic hierarchy is established because HLDA is based on the Nested Chinese Restaurant Process (NCRP), a tree extension to Chinese Restaurant Process, which probabilistically generates a partition of a set {1, 2, ......, n} at time n. In NCRP, a document is considered as a Chinese restaurant traveler who visits L restaurants along a restaurant tree path, where L refers to the level of the tree (i.e., the length of the path).

We decompose the labeling process into two sub-processes of establishing topics and labeling users with the established topics. In the first topic establishment step, we run LDA after removing popular users from the dataset similar to how we remove stop words before applying LDA to a document corpus. This step generates clean topics free from the noise generated by popular users. In the second labeling step, we apply LDA only to popular users in the dataset. As we use the collapsed Gibbs sampling algorithm [21], edges to popular users are labeled according to the pre-established topics as represented in Equation (4).

where P(e(f, g) = z|. ) denotes the probability of labeling the edge from a follower f to the followed user g with a topic z, given all conditions, N_gz denotes the number of times g is labeled with z, and N_fz denotes the number of times f is labeled with z.

As briefly described in Section 3.1, the association between a user (a word) and a topic has varying association strengths represented by P(g|z) (P(w|z)) in a probabilistic topic model. Thus, we can list users labeled with the same topic in descending order of P(g|z) and regard the top entries in the list (topic group) as more important than the entries at the bottom because they are more strongly associated with the topic. Similarly, we can measure the association strength from the user's viewpoint using P(z|g). Though two-step labeling may help label popular users with the right topics, popular users may take top positions even in less-relevant topic groups because even the smallest number of times a popular user is assigned to a topic group could outnumber the largest number of times a non-popular user is assigned to that topic group.

To mitigate this problem, we propose a new approach, threshold noise filtering, which sets a cut-off value to determine whether to label a user with each topic. By ignoring assignments below the cut-off value, we can expect smoothing and noise reduction effects as in the anti-aliasing filter.

We set N_gizk, the number of times a followed user g_i is assigned to a topic group z_k, as 0 if it is below the cut-off value C:

As threshold noise filtering process is done after sampling, it does not increase computational complexity similar to two-step labeling.

Alternatively, we may filter out less relevant topics by keeping only the top-K topics for each user, for a reasonably small K value. We tested both schemes (threshold noise filtering and top-K filtering), but we couldn't see any practical differences.

Though threshold noise filtering can be used with any other approaches, we combine it with the two most representative cases, two-step labeling and the standard LDA in our experiments.

For our experiments, we use a Twitter dataset we collected between October 2009 and January 2010. The original downloaded dataset contained 273 million follow edges, but we sampled 10 million edges from this dataset to keep our experiment manageable. To ensure that all the follow edges were preserved in our sampled dataset, we first sampled followers randomly and included all follow edges from the sampled users, until we obtained 10 million follow edges.

From the graph, it is clear that the number of incoming edges follows a power-law distribution, which is often the case for this type of dataset. Interestingly, we observe that the number of outgoing edges is quite uniform between edge counts 1 to 100, which is different from the distribution reported in [14]. We do not believe this difference is due to our sampling, because the graph from the complete dataset shows the same at curve between the edge counts 1 and 100 [25].

Perplexity is a well-known standard metric used in IR. It tries to quantify the accuracy of a model by measuring how well the trained model deals with an unobserved test data. More precisely, perplexity is defined to be [26]:

where E_test denotes all the edges in the test dataset. We calculated Perplexity values for the 10% held-out dataset after training the models on the remaining 90% dataset. In general, lower perplexity means better generalizability.

Note that the original LDA model is designed to derive an optimal model that minimizes perplexity. Therefore, it is unlikely that extensions to base LDA show lower perplexity. Our primariy goal of comparing the results under the perplexity metric is to see whether our proposed extensions significantly degrade perplexity.

From the graphs, we first notice that HLDA (hlda-3lv and hlda-2lv) shows significantly worse Perplexity than others. This is due to the fact that the standard LDA is designed to minimize Perplexity while HLDA is not necessarily designed for this task.

Overall, we find that our two-step labeling and threshold noise filtering show similar perplexity values to the standard LDA model. That is, our extensions to LDA do not introduce noticeable Perplexity degradation to the standard LDA model.

To measure human-perceived quality, we conducted a survey with a total of 14 participants. The participants in our survey were presented with a random group of ten Twitter users (identified by one of the eight approaches described in Section 5.1) and were asked to indicate if each user in the topic group was relevant to the group or not. Overall, we collected 23 judged topic groups per each approach with a total of 161 judged topic groups.

Both of our extensions, two-step labeling and threshold noise filtering are very effective in improving the human-perceived quality of identified topic groups.

As two-step filtering initially forms clean topics free from popular user generated noise, its gain is more significant than that of threshold noise filtering. However, threshold noise filtering can be easily combined with any other approaches to improve Quality, as in filter-base.

If we apply the standard LDA to popular users as well without any pre-filtering, the produced topic groups are quite noisy.

Using an asymmetric Dirichlet prior for the hyperparameter β improves Quality, but the result is still noisier compared to our extensions.

The HLDA model shows only marginal improvements in the Quality metric when compared to base. This low performance is because most of the low-level groups in HLDA have users with very few followers (who are less likely to be interesting when recommended) and contribute only small weights to Quality.

Note that many users in this group are very popular and they are mainly about the same topic, tech media, indicating that 2step is able to group popular users into the right topic group in general. However, we observe that 2step still su ers from the presence of a few popular, yet less relevant users in the group (in this example, cnnbrk and breakingnews may be considered less relevant to the group than others)

With threshold noise filtering, we achieved less noisy results. Figure 12 shows a result topic group from filter-2step corresponding to the group in Figure 11 from 2step. We observe that cnnbrk and breakingnews, popular users on general media, are now removed from Figure 11 and more technology-centric media such as firefox, youtube, and engadget are added.

Even with this relatively limited type of data compared to those of previous approaches, our approaches generated very well-organized results and showed the great potential of applying LDA to these kinds of clustering applications. Our approaches are especially useful when only linkage data is available.

Ellison, N. B., Steinfield, C. and Lampe, C. (2007). The benefits of Facebook ‘‘Friends:’’ Social capital and college students’ use of online social network sites. Journal of Computer-Mediated Communication, 12, 1143-1168.

Ellison, N. B., Steinfield, C. and Lampe, C. (2007). The benefits of Facebook ‘‘Friends:’’ Social capital and college students’ use of online social network sites. Journal of Computer-Mediated Communication, 12, 1143-1168.

community and communication

過去的社會媒體研究常以使用者能夠藉由社會媒體拓展其人際關係，進而從線上發展為線下的人際關係。本論文則認為社會媒體將使線下的人際關係發展為線上的人際關係。作者分析大學生使用Facebook與形成或維繫其社會資本(social capital)之間的關連，並且也探討這些因素和自尊(self-esteem)與生活滿意度(life satisfaction)間的互動關係。過去的研究一般認為社會資本是指從人際關係累積的資源，其資源對個人或一個群體是由其所擁有的網路累積而成(Bourdieu and Wacquant, 1992)。本研究引用Putnam (2000)以關係的親近與有無提供情感支持(emotional supoort)對於社會資本的區別，並且強調線上網路工具使個人在離開後仍然能夠接觸原先社會網路的功能，因此本研究將其研究對象的社會資本分為：1)橋接社會資本(bridging social capital)；2)黏著社會資本(bonding social capital)；3)維繫社會資本(maintained social capital)。本研究以線上問卷蒐集大學生的Facebook使用經驗與他們的社會資本，有回應的受訪者共計286位(佔全體的35.8%)，其中大多數(94%)的使用者都有使用Facebook的經驗。研究結果發現：Facebook使用於所涉及的人為有共同的線下關連(平均3.64)比結識新朋友(平均1.97)更多(t = 26.14, p , .0001)，因此可以說明Facebook多用於維繫現有的線下關係和鞏固暫時結識的友誼。處在低生活滿意度和低自尊的學生如果能夠更多地使用Facebook，能夠從此獲益於橋接社會資本。學生的黏著社會資本和維繫社會資本也能從他們使用Facebook的強度來預測。

This study examines the relationship between use of Facebook, a popular online social network site, and the formation and maintenance of social capital.

Regression analyses conducted on results from a survey of undergraduate students (N = 286) suggest a strong association between use of Facebook and the three types of social capital, with the strongest relationship being to bridging social capital.

In addition, Facebook usage was found to interact with measures of psychological well-being, suggesting that it might provide greater benefits for users experiencing low self-esteem and low life satisfaction.

Previous research suggests that Facebook users engage in ‘‘searching’’ for people with whom they have an offline connection more than they ‘‘browse’’ for complete strangers to meet (Lampe, Ellison, & Steinfield, 2006).

Social capital broadly refers to the resources accumulated through the relationships among people (Coleman, 1988).

Bourdieu and Wacquant (1992) define social capital as ‘‘the sum of the resources, actual or virtual, that accrue to an individual or a group by virtue of possessing a durable network of more or less institutionalized relationships of mutual acquaintance and recognition’’ (p. 14)

Social capital has been linked to a variety of positive social outcomes, such as better public health, lower crime rates, and more efficient financial markets (Adler & Kwon, 2002). ... Greater social capital increases commitment to a community and the ability to mobilize collective actions, among other benefits. Social capital may also be used for negative purposes, but in general social capital is seen as a positive effect of interaction among participants in a social network (Helliwell & Putnam, 2004).

Moreover, social capital researchers have found that various forms of social capital, including ties with friends and neighbors, are related to indices of psychological well-being, such as self esteem and satisfaction with life (Bargh & McKenna, 2004; Helliwell & Putnam, 2004).

Putnam (2000) distinguishes between bridging and bonding social capital. The former is linked to what network researchers refer to as ‘‘weak ties,’’ which are loose connections between individuals who may provide useful information or new perspectives for one another but typically not emotional support(Granovetter, 1982). Alternatively, bonding social capital is found between individuals in tightly-knit, emotionally close relationships, such as family and close friends.

This concept, ‘‘maintained social capital,’’ permits us to explore whether online network tools enable individuals to keep in touch with a social network after physically disconnecting from it.

Donath and boyd (2004) hypothesize that SNSs could greatly increase the weak ties one could form and maintain, because the technology is well-suited to maintaining such ties cheaply and easily.

... a 2006 Pew Internet survey reports that online users are more likely to have a larger network of close ties than non-Internet users, and that Internet users are more likely than non-users to receive help from core network members (Boase, Horrigan, Wellman, & Rainie, 2006).

Some forms of computer-mediated communication can lower barriers to interaction and encourage more self-disclosure (Bargh, McKenna, & Fitzsimons, 2002; Tidwell & Walther, 2002); hence, these tools may enable connections and interactions that would not otherwise occur.

Wellman et al. (2001), for example, find that heavy Internet users rely on email to maintain long distance relationships, rather than using it as a substitute for offline interactions with those living nearby.

A total of 286 students completed the online survey, yielding a response rate of 35.8% (see Table 1 for sample demographics).

According to Williams (2006), ‘‘members of weak-tie networks are thought to be outward looking and to include people from a broad range of backgrounds. The social capital created by these networks generates broader identities and generalized reciprocity’’ (n.p.).

From Table 3 we see that respondents also report significantly more Facebook use involving people with whom they share an offline connection— either an existing friend, a classmate, someone living near them, or someone they met socially (mean = 3.64)—than use involving meeting new people (mean = 1.97) (t = 26.14, p , .0001).

This suggests that students use Facebook primarily to maintain existing offline relationships or to solidify what would otherwise be ephemeral, temporary acquaintanceships. There was a slight tendency for newer students to use Facebook to meet new people more than for juniors and seniors to do so (see Figure 3), but across all four years in school, respondents reported greater use of Facebook for connecting with existing offline contacts.

The results suggest that Facebook is indeed implicated in students’ efforts to develop and maintain bridging social capital at college, although we cannot assess causal direction. ... Among the psychological measures, the extent of students’ satisfaction with life at MSU was strongly correlated with bridging social capital (scaled beta = .66, p <.0001).

Students reporting low satisfaction and low self-esteem appeared to gain in bridging social capital if they used Facebook more intensely, suggesting that the affordances of the SNS might be especially helpful for these students.

As shown in Table 7, bonding social capital was also significantly predicted by the intensity with which students used Facebook (scaled beta = .37, p < .001 in model 2).

Finally, entering only our control factors accounted for 13% of the variance in maintained social capital (Table 8). Adding Facebook intensity raised the R² to .17 and revealed the same strong connection to Facebook intensity (scaled beta = .36, p <.001), even after controlling for the number of years at college (and thus, away from high school) and general Internet use.

Our findings suggest that certain kinds of Facebook use (articulated by our Facebook intensity items) can help students accumulate and maintain bridging social capital.

One explanation consistent with these interaction effects is that Facebook use may be helping to overcome barriers faced by students who have low satisfaction and low self-esteem. Because bridging social capital provides benefits such as increased information and opportunities, we suspect that participants who use Facebook in this way are able to get more out of their college experience.

However, Facebook appears to be much less useful for maintaining or creating bonding social capital, as indicated by the fact that the bonding model only accounted for 22% of the variance (versus 46% in the bridging social capital models).

Finally, Facebook intensity predicted increased levels of maintained social capital, which assessed the extent to which participants could rely on high school acquaintances to do small favors. For college students, many of whom have moved away for the first time, the ability to stay in touch with these high school acquaintances may illustrate most clearly the ‘‘strength of weak ties’’ outlined by Granovetter (1973, 1982). These potentially useful connections may be valuable sources of new information and resources.