Rosen-Zvi, M., Griffiths, T., Steyvers, M., & Smyth, P. (2004, July). The author-topic model for authors and documents. In Proceedings of the 20th conference on Uncertainty in artificial intelligence (pp. 487-494). AUAI Press.

Rosen-Zvi, M., Griffiths, T., Steyvers, M., & Smyth, P. (2004, July). The author-topic model for authors and documents. In Proceedings of the 20th conference on Uncertainty in artificial intelligence (pp. 487-494). AUAI Press.

本研究提出作者-主題模型(author-topic model)，這是一個擴充LDA (Latent Dirichlet Allocation; Blei, Ng, & Jordan, 2003) 並加入作者資訊的文件產生模型。和基本的LDA相同的是都用一組的主題混合(mixture)來代表每一筆文件，但這個模型具有能夠由文件的作者決定表現文件上不同主題的混合權重(mixture weights)的特性。為了進一步說明這個模型，本研究比較了基礎的LDA、作者模型以及作者-主題模型的文件產生過程。首先，LDA的文件產生過程包含三個步驟：首先由一個Dirichlet分布中取樣，產生每一筆文件的主題分布；其次在產生文件中的每一個詞語之前，先從上面的主題分布中選取一個主題；最後從選定的主題對應的詞語分布上取樣產生這個詞語。整個模型如下圖所示

在這個模型裡，ϕ表示主題分布的矩陣，利用一個由詞彙裡的V個詞語的多元常態分布來表示T個主題中的每一個主題，而這些多元常態分布是從一個Dirichlet分布Dirichlet(β)中獨立地抽取而形成的。θ是文件上T個主題的混合權重所組成的矩陣，每一個文件的主題混合權重都是由一個Dirichlet分布Dirichlet(α)中獨立地抽取而形成的。最後，每一個文件中的詞語有一個相對應的主題z，z是從文件相對應的主題混合權重θ取樣產生，而這個詞語則是根據主題z所對應的主題分布ϕ 所產生。運用演算法推導文件的產生模型，估算ϕ和θ可以分別提供語料中具有的主題以及這些主題在各個文件上的權重等資訊，常用的演算法包括變異推論(variational inference; Blei et al., 2003)、期望值延遲(expectation propagation; Minka & Laerty, 2002)和Gibbs取樣(Gibbs sampling; Griffiths & Steyvers, 2004)等。

作者模型如下圖所示

這個模型假設某一篇文件是由一群作者a_d共同撰寫，某一位作者都擁有一套本身習慣使用的詞語組合，這個詞語組合可以由詞語的機率分布ϕ來描述，從一個Dirichlet分布Dirichlet(β)中獨立地抽取而形成的。在產生文件時，文件上的每一個詞語由a_d中依據均勻分布(uniform distribution)隨機選取某一位作者x所撰寫，而詞語產生的機率便是由作者x對應的詞語機率分布來決定。因此若能估算ϕ，便能提供有關作者的研究興趣方面的資訊，並且進而從作者撰寫的文件內容的相似性估計他們在研究主題上的相似性。然而這個模型的問題是興趣主題的估算僅受限於作者所撰寫過的文件內容上的詞語，無法進一步擴及相同主題但使用不同詞語的文件。

作者-主題模型整合上述兩個模型。這個模型如同作者模型假設文件上的每一個詞語由一群共同作者a_d中依據均勻分布(uniform distribution)隨機選取某一位作者x撰寫，但作者-主題模型假定每位作者本身擁有一套主題組合θ，θ上的機率分布是從Dirichlet(α)中獨立地抽取而形成的。所以在產生每一個詞語之前，先根據選定的作者x對應的主題機率分布θ挑選一個主題z，然後再根據這個主題對應的詞語分布機率ϕ挑選出一個詞語w做為輸出，詞語分布機率ϕ的產生則是由Dirichlet(β)中獨立地抽取而成。作者-主題模型如下圖所示

本研究運用Gibbs取樣推估各種模型的參數，這種方法提供根據Dirichlet先驗機率(prior)獲得參數估計的簡單方法並且允許從許多後驗機率分布(posterior distribution)的局部最大值(local maxima)組合估計值。

首先是LDA模型，這個模型包含兩組未知的參數：θ和ϕ，以及隱藏的變數(latent variables)也就是指定給每一個詞語的主題z。通過採用在z上的Gibbs取樣(Gilks, Richardson, & Spiegelhalter, 1996)，可以構建一個Markov鏈(Markov chain)，並且這個Markov鏈收斂後驗分布(posterior distribution)，然後利用這些結果推斷θ和ϕ(Griffths & Steyvers, 2004)。在Markov鏈接續狀態間的轉移是來自於重複從以所有其他變數為條件下的分布上抽取z的結果。如下面的式子

此處z_i = j代表文件的第i個詞語指定為主題j的情形；w_i = m則代表第i個詞語實際上是詞彙中的詞語m的情形，z_-i表示不包括第i個詞語的所有詞語的主題指定情形。C^WT_mj是不包括目前的案例下，詞語m被指定為主題j的次數，C^DT_dj則是不包括目前的案例下，主題j出現在文件d的次數。然後運用上面的式子產生Markov鏈，從上取樣所有訓練文件內各詞語的指定主題，並估算θ和ϕ。

此處ϕ_mj是在主題j中使用詞語m的機率，θ_dj 則是主題j在文件d中的機率。

運用同樣的方式來推測作者模型的未知參數ϕ，這個模型的隱藏變數是文件中每一個詞語所指定的作者x。在Markov鏈接續狀態間的轉移是在以所有其他變數為條件下的分布上重複抽取x的結果

此處x_i = k 代表將第i個詞語指定為作者k的情形， C^WA_mk則是不包括目前的案例下，詞語m被指定為作者k的次數。所以作者k使用詞語m的機率可以用下面的式子推估



在作者-主題模型方面，這個模型包括兩組隱藏變數z和x，在其他已知與未知變數的條件下，針對某一個詞語w_i分別指定作者x_i為k 與主題z_i為j的機率

此處z_-i,x_-i代表不包括第i個詞語的所有詞語的主題與作者指定情形。C^AT_kj 是不包括目前的案例下，作者k被指定為主題j的次數。根據上面的式子，給定主題j，詞語m被選取的機率ϕ_mj與給定作者k，主題j被選取的機率分別可以用下面的式子進行估算。



本研究以兩個資料集NIPS與Citeseer進行實驗，對作者-主題模型所發現的每一個主題，以從對應的主題機率分布內選取機率較高的詞語為該主題的標示，同時並選取該主題機率較高的代表作者。結果發現標示詞語大多能夠具體地代表不同的主題，而作者也大多是該主題非常知名的作者。NIPS資料集共計有1740篇研究會論文，共2037位作者，論文中所用的詞彙包括13649種詞語，資料集實際出現的詞語共有2301375次；CiteSeer資料集共計有162489篇論文摘要，共85465位作者，摘要中所用的詞彙包括30799種詞語，資料集實際出現的詞語共有11685514次。此外，本研究並且利用複雜度(perplexity)比較三種模型在詞語預測的成效。複雜度的計算如下

複雜度愈低表示該模型在詞語預測成效愈好。結果發現作者模型因為受限於模型本身概化的能力(generalization)較弱，所得到的成效比其他兩種主題模型差。因為加入來自作者的資訊，作者-主題模型在少量的訓練資料下有LDA較好的成效；當訓練語料增加，LDA便有較低的複雜度，並且當模型的主題數更多時，LDA需要的訓練語料更少。最後，本研究利用對稱 KL差異度(symmetric KL-divergence)測量作者的研究主題相似性，

並且利用熵(entropy)測量作者的研究主題分布廣度。

In our results we used two text data sets consisting of technical papers|full papers from the NIPS conference and abstracts from CiteSeer (Lawrence, Giles, & Bollacker, 1999). ... This leads to a vocabulary size of V = 13,649 unique words in the NIPS data set and V = 30,799 unique words in the CiteSeer data set. Our collection of NIPS papers contains D = 1,740 papers with K = 2,037 authors and a total of 2,301,375 word tokens. Our collection of CiteSeer abstracts contains D = 162,489 abstracts with K = 85,465 authors and a total of 11,685,514 word tokens.

We introduce the author-topic model, a generative model for documents that extends Latent Dirichlet Allocation (LDA; Blei, Ng, & Jordan, 2003) to include authorship information. Each author is associated with a multinomial distribution over topics and each topic is associated with a multinomial distribution over words. A document with multiple authors is modeled as a distribution over topics that is a mixture of the distributions associated with the authors.

We apply the model to a collection of 1,700 NIPS conference papers and 160,000 CiteSeer abstracts.

Recently, generative models for documents have begun to explore topic-based content representations, modeling each document as a mixture of probabilistic topics (e.g., Blei, Ng, & Jordan, 2003; Hofmann, 1999).

With an appropriate author model, we can establish which subjects an author writes about, which authors are likely to have written documents similar to an observed document, and which authors produce similar work.

This generative model represents each document with a mixture of topics, as in state-of-the-art approaches like Latent Dirichlet Allocation (Blei et al., 2003), and extends these approaches to author modeling by allowing the mixture weights for different topics to be determined by the authors of the document.

In LDA, the generation of a document collection is modeled as a three step process. First, for each document, a distribution over topics is sampled from a Dirichlet distribution. Second, for each word in the document, a single topic is chosen according to this distribution. Finally, each word is sampled from a multinomial distribution over words specific to the sampled topic.

This generative process corresponds to the hierarchical Bayesian model shown (using plate notation) in Figure 1(a).



In this model, ϕ denotes the matrix of topic distributions, with a multinomial distribution over V vocabulary items for each of T topics being drawn independently from a symmetric Dirichlet(β) prior. θ is the matrix of document-specific mixture weights for these T topics, each being drawn independently from a symmetric Dirichlet(α) prior. For each word, z denotes the topic responsible for generating that word, drawn from the θ distribution for that document, and w is the word itself, drawn from the topic distribution ϕ corresponding to z.

Estimating ϕ and θ provides information about the topics that participate in a corpus and the weights of those topics in each document respectively.

A variety of algorithms have been used to estimate these parameters, including variational inference (Blei et al., 2003), expectation propagation (Minka & Laerty, 2002), and Gibbs sampling (Griffiths & Steyvers, 2004).

Assume that a group of authors, a_d, decide to write the document d. For each word in the document an author is chosen uniformly at random, and a word is chosen from a probability distribution over words that is specific to that author.

x indicates the author of a given word, chosen uniformly from the set of authors a_d. Each author is associated with a probability distribution over words ϕ, generated from a symmetric Dirichlet(β) prior. Estimating ϕ provides information about the interests of authors, and can be used to answer queries about author similarity and authors who write on subjects similar to an observed document.

However, this author model does not provide any information about document content that goes beyond the words that appear in the document and the authors of the document.

As in the author model, x indicates the author responsible for a given word, chosen from a_d. Each author is associated with a distribution over topics, θ, chosen from a symmetric Dirichlet(α) prior. The mixture weights corresponding to the chosen author are used to select a topic z, and a word is generated according to the distribution ϕ corresponding to that topic, drawn from a symmetric Dirichlet(β).

In this paper, we will use Gibbs sampling, as it provides a simple method for obtaining parameter estimates under Dirichlet priors and allows combination of estimates from several local maxima of the posterior distribution.

The LDA model has two sets of unknown parameters -- the D document distributions θ, and the T topic distributions ϕ -- as well as the latent variables corresponding to the assignments of individual words to topics z. By applying Gibbs sampling (see Gilks, Richardson, & Spiegelhalter, 1996), we construct a Markov chain that converges to the posterior distribution on z and then use the results to infer θ and ϕ (Griffths & Steyvers, 2004). The transition between successive states of the Markov chain results from repeatedly drawing z from its distribution conditioned on all other variables, summing out θ and ϕ using standard Dirichlet integrals:

where z_i = j represents the assignments of the ith word in a document to topic j , w_i = m represents the observation that the ith word is the mth word in the lexicon, and z_-i represents all topic assignments not including the ith word. Furthermore, C^WT_mj is the number of times word m is assigned to topic j, not including the current instance, and C^DT_dj is the number of times topic j has occurred in document d, not including the current instance.

For any sample from this Markov chain, being an assignment of every word to a topic, we can estimate and using


where ϕ_mj is the probability of using word m in topic j, and θ_dj is the probability of topic j in document d. These values correspond to the predictive distributions over new words w and new topics z conditioned on w and z.

An analogous approach can be used to derive a Gibbs sampler for the author model.

where x_i = k represents the assignments of the ith word in a document to author k and C^WA_mk is the number of times word m is assigned to author k.



In the author-topic model, we have two sets of latent variables: z and x. We draw each (z_i, x_i) pair as a block, conditioned on all other variables:

where z_i = j and x_i = k represent the assignments of the ith word in a document to topic j and author k respectively, w_i = m represents the observation that the ith word is the mth word in the lexicon, and z_-i,x_-i represent all topic and author assignments not including the _ith word, and C^AT_kj is the number of times author k is assigned to topic j, not including the current instance.

Equation 4 is the conditional probability derived by marginalizing out the random variables ϕ (the probability of a word given a topic) and θ (the probability of a topic given an author).




In the examples considered here, we do not estimate the hyperparameters α and β instead the smoothing parameters are fixed at 50/T and 0.01 respectively.

We start the algorithm by assigning words to random topics and authors (from the set of authors on the document). Each iteration of the algorithm involves applying Equation 4 to every word token in the document collection, which leads to a time complexity that is of order of the total number of word tokens in the training data set multiplied by the number of topics, T (assuming that the number of authors on each document has negligible contribution to the complexity).

In our results we used two text data sets consisting of technical papers|full papers from the NIPS conference and abstracts from CiteSeer (Lawrence, Giles, & Bollacker, 1999). ... This leads to a vocabulary size of V = 13,649 unique words in the NIPS data set and V = 30,799 unique words in the CiteSeer data set. Our collection of NIPS papers contains D = 1,740 papers with K = 2,037 authors and a total of 2,301,375 word tokens. Our collection of CiteSeer abstracts contains D = 162,489 abstracts with K = 85,465 authors and a total of 11,685,514 word tokens.

Perplexity is a standard measure for estimating the performance of a probabilistic model. The perplexity of a set of test words, (w_d, a_d) for d ∈ D^test, is defined as the exponential of the negative normalized predictive likelihood under the model,



Better generalization performance is indicated by a lower perplexity over a held-out document.

The author model is clearly poorer than either of the topic-based models, as illustrated by its high perplexity. Since a distribution over words has to be estimated for each author, fitting this model involves finding the values of a large number of parameters, limiting its generalization performance.

The author-topic model has lower perplexity early on (for small values of N^(train)_d ) since it uses knowledge of the author to provide a better prior for the content of the document. However, as N^(train)_d increases we see a cross-over point where the more flexible topic model adapts better to the content of this particular document.

For larger numbers of topics, this crossover occurs for smaller values of N^(train)_d , since the topics pick out more specific areas of the subject domain.

One can see that making use of the authorship information significantly improves the predictive log-likelihood: the model has accurate expectations about the content of documents by particular authors.

Such a task requires computing the similarity between authors. To illustrate how the model could be used in this respect, we defined the distance between authors i and j as the symmetric KL divergence between the topics distribution conditioned on each of the authors:

The topic distributions for different authors can also be used to assess the extent to which authors tend to address a single topic in their work, or cover multiple topics. We calculated the entropy of each author's distribution over topics on the NIPS data, for different numbers of topics.

When compared to the LDA topic model, the author-topic model was shown to have more focused priors when relatively little is known about a new document, but the LDA model can better adapt its distribution over topics to the content of individual documents as more words are observed.

Zhang, H., Qiu, B., Giles, C. L., Foley, H. C., & Yen, J. (2007, May). An LDA-based community structure discovery approach for large-scale social networks. In Intelligence and Security Informatics, 2007 IEEE (pp. 200-207). IEEE.

Zhang, H., Qiu, B., Giles, C. L., Foley, H. C., & Yen, J. (2007, May). An LDA-based community structure discovery approach for large-scale social networks. In Intelligence and Security Informatics, 2007 IEEE (pp. 200-207). IEEE.

本研究以LDA (latent Dirichlet allocation) 演算法[17]做為社群發現(community discovery)的方法，也就是找出社會網路上在群體內高度相連但在群體間相對稀疏的行動者(actors)社群。在這個方法裡，社群被視為是LDA模型裡的隱藏變數，由所有行動者依不同比例組合成的混合(mixtures)。本研究認為這個方法的優點是只需要利用網路的型態資訊(topological information)便可進行社群發現；此外，有別於[2, 3, 5]等先前的方法，這個方法能夠描述行動者屬於多個社群的現象，並且在每個社群上有不同重要性。

本研究將所有與某個行動者互動的行動者以及他們之間的社會互動情形定義為這個行動者的社會互動特徵(social interaction profile, sip)，例如行動者v_i的社會互動特徵定義為

SIW(v_i, w_ij)是行動者v_i與另一位行動者w_ij間的互動情形，m_i是與v_i互動的行動者數目。
在利用LDA模型進行社群發現時，將每個行動者的社會互動特徵視為是原先模型中的文件，這些行動者發生的互動則是模型中的詞語，值得一提的是在社會網路上行動者間的互動順序是可以交換的(exchangeable)，因此LDA模型相當適合這種情形。下圖是這個模型的圖示，


對行動者v_i而言，其社會互動特徵sip_i的產生過程(generative process)如下
1) Sample mixture components ϕ_k ~ Dir(β) for k (belongs) [1, K]
2) Choose θ_i ~ Dir(α)
3) Choose N_i ~ Poisson(ξ) (note that Poisson assumption is not critical to this model)
4) For each of the N_i social interactions w_ij :
(a) Choose a community ι_ij ~ Multinomial(θ_i);
(b) Choose a social interaction w_ij ~ Multinomial(ϕ_ιij)
也就是
1) 從Dir(β)中產生行動者的組合ϕ_k來代表K個社群中每一個社群；
2) 從Dir(α)中選擇一個社群的組合θ_i，做為所有與v_i互動的行動者所可能屬於的社群的分布情形；
3) 從Poisson(ξ)中選擇社會互動的個數N_i ；
4) 產生每一個社會互動 w_ij時：
a) 從Multinomial(θ_i)中選擇一個社群ι_ij；
b) 從Multinomial(ϕ_ιij)中選擇一個社會互動 w_ij。

根據這個模型，行動者v_i的社會互動特徵sip_i中的第j個社會互動元素w_ij為w_m的機率是

此處θ_i是sip_i 的混合比變數(mixing proportion variable)，而ϕ_k是第k個社群成分分布(component distribution)的參數集合。

給定超參數(hyperparameter)α和β後，所有已知和隱藏變數的聯合機率(joint probability)為

由於要精確地推論LDA模型的變數一般而言是很困難的(intractable)，因此經常以 變異期望值最大化(variational expectation maximization) [17], 期望值延遲 (expectation propagation) [24]和 Gibbs取樣 (Gibbs sampling) [25], [26], [22]等三種方法取得近似解。本研究採用的方法是Gibbs取樣，以Markov鏈 Monte Carlo模擬(Markov-chain Monte Carlo simulation)的方式，去逼近ϕ_k,w和θ_m,k等變數


本研究針對CiteSeer和NanoSCI兩個書目資料集中的作者合著網路(co-authorship networks)上最大的成分進行社群發現，其中CiteSeer部分共包含249866個節點，而NanoSCI則有203762個節點。本研究並且提出了01-SIP、012-SIP和 k-SIP等三種描述行動者間的社會互動情形，01-SIP是描述兩個作者有直接合著的社會互動情形，如果兩個作者曾經合著至少一篇論文，便將他們的互動情形設為1，否則便設為0；012-SIP則考慮兩個作者沒有直接合著但曾經分別和第三位作者合著的情形，如果兩個作者曾經合著至少一篇論文，便將他們的互動情形設為2，雖然這兩位作者不曾合著，但曾有分別和第三位作者合著，便將互動情形設為2，否則便設為0；k-SIP則描述兩位作者多次合著的情形，k是他們合著的次數。研究結果發現在複雜度(perplexity)與各產生社群的緊密度(compactness of communities)等指標，012-SIP的成效都比其他兩者好，從社群發現的結果可以發現許多社群裡的作者是屬於相同的研究機構或是彼此具有相似的研究興趣，因此會共同研究並且合作發表而成為社群。

This paper describes an LDA(latent Dirichlet Allocation)-based hierarchical Bayesian algorithm, namely SSN-LDA(Simple Social Network LDA). In SSN-LDA, communities are modeled as latent variables in the graphical model and defined as distributions over the social actor space. The advantage of SSN-LDA is that it only requires topological information as input.

This model is evaluated on two research collaborative networks: CiteSeer and NanoSCI. The experimental results demonstrate that this approach is promising for discovering community structures in large-scale networks.

An important task in these emerging networks is community discovery, which is to identify subsets of networks such that connections within each subset are dense and connections among different subsets are relatively sparse.

Unlike those previous community discovery studies, we design a hierarchical Bayesian network based approach, namely SSN-LDA (Simple Social Network-LDA) to discover probabilistic communities from social networks. ... In this model, communities are modeled as latent variables and are considered as distributions on the entire social actor space.

We also propose three different approaches to create social interaction profiles based on the social interaction information in the network.

Girvan et al extended this measure to edges and designed a clustering algorithm which gradually remove the edges with highest betweenness value [5]. ... However, a major problem with this approach is that the complexity of this approach is O(m²n), where m is the number of edges in the graph and n is the number of vertices in the network.

The graph partition problem can be formulated as the balanced minimum cut problem where the goal is to find an optimal graph partition so that the edge weight between the partitions is minimized while maintaining partitions of a minimal size. The NP-complete complexity of this approach [15] requires approximate solutions. Flake et al developed approximate algorithms to partition the network by solving s-t maximum flow techniques [2], [3]. The main idea behind maximum flow is to create clusters that have small inter-cluster cuts and relatively large intra-cluster cuts.

The major difference between SSN-LDA approach and the aforementioned approaches is that SSN-LDA is a mixture-model based probabilistic approach. Each community weighs in the contributions from every social actors and this property can be exploited in many potential applications that will be introduced in Section VI.

LDA model was first introduced by Blei for modeling the generative process of a document corpus [17].

Among these variants of LDA models, the approaches proposed in [20], [10] are both concerned about the authors of the documents in the corpus. In particular, Zhou et al introduced a community latent variable in their graphical model and applied it to discover community information embedded in document corpus. This approach can discover the underlying social network based on social interactions and topical similarity.

In their follow-up work[23], Zhou et al. investigated how research topics evolve over time and attempted to discover the most influential researchers involved in such transitions.

Each actor is characterized by its social interaction profile (SIP), which is defined as a set of neighbor(w_ij) and the corresponding weight(SIW(v_i, w_ij)) pair.

where m_i is the size of v_i's social interaction profile.

Note that we consider the social interaction elements in this profile are exchangeable and therefore their order will not be concerned. It is this exchangeability that permits the application of LDA model [17].

Subsequently, we specify that a social network contains a set of communities ι (ι1, ι2, …, ιk) and each community in ι is defined as a distribution on the social actor space. In SSN-LDA, community assignments are modeled as a latent variable (ι) in the graphical model. The community proportion variable (θ) is regulated by a Dirichlet distribution with a known parameter α. Meanwhile, each social actor belongs to every community with different probabilities and therefore its social interaction profiles can be represented as random mixtures over latent communities variables.

The SSN-LDA model for social network analysis is illustrated in Fig. 1. Note that SSN-LDA resembles topic-based LDA model[17], with the social network being analogous to the corpus, the social interaction profiles being analogous to documents; and the occurrence of social interactions being analogous to words.

The distribution of topics in documents and the terms over topics are two multinomial distributions with two Dirichlet priors, whose hyperparameters are α and β respectively.

The dimensionality K of the Dirichlet distribution, which is also the number of community component distributions, is assumed to be known and fixed.

This generative process for an agent(w_i)'s social interaction profile sip_i in a social network is:
1) Sample mixture components ϕ_k ~ Dir(β) for k (belongs) [1, K]
2) Choose θ_i ~ Dir(α)
3) Choose N_i ~ Poisson(ξ) (note that Poisson assumption is not critical to this model)
4) For each of the N_i social interactions w_ij :
(a) Choose a community ι_ij ~ Multinomial(θ_i);
(b) Choose a social interaction w_ij ~ Multinomial(ϕ_ιij)

According to the model, the probability that the jth social interaction element w_ij in the social actor w_i's social interaction profile sip_i instantiates a particular neighboring agent w_m is:

where θ_i is the mixing proportion variable for sip_i and ϕ_k is the parameter set for the kth community component distribution.

Given the hyperparameters α and β, the joint distribution of all known and hidden variables is:


Exact inference is generally intractable for LDA model. There have been three major approaches for solving this model approximately, including variational expectation maximization [17], expectation propagation [24], and Gibbs sampling[25], [26], [22].

Gibbs sampling is a special case of Markov-chain Monte Carlo (MCMC) simulation[27] where the dimension K of the distribution are sampled alternately one at a time, conditioned on the values of all other dimensions[22].

we apply the Gibbs sampling algorithm that has been introduced in [26], [22] to solve the SSN-LDA model and reduce the computation requirement.



Subsequently, the update equation for the hidden variable can be derived [22]:


where n^(.)_⌐i is the count that does not include the current assignment of ι_i and recall that sip is the variable for social interaction profiles. For the sake of simplicity, we assume that the Dirichlet distribution is symmetric in deriving the above formula.

Finally, the update formula for ϕ_k,w and θ_m,k are as follows:



In co-authorship networks, the vertices represent researchers and the edges in the network represent the collaboration relation between researchers. In this section we evaluate SSNLDA model on co-authorship networks collected from two distinct areas: computer science(CiteSeer) and nanotechnology(NanoSCI). Note that no name disambiguation has been done on either dataset.

The size of the largest connected subnetwork of CiteSeer is 249866 while the size of the largest connected subnetwork in NanoSCI is 203762. In this paper, we are only interested in discovering community structures in the two largest subnetworks.

In this paper, we explore three different types of social interaction pro le representations for social networks, namely 01-SIP, 012-SIP, and k-SIP.

In the 01-SIP approach, an edge is drawn between a pair of scientists if they coauthored one or more articles. Collaborating multiple times does not make a difference in this model

In order to mitigate this problem, we propose a 012-SIP model which takes a node's neighbors' neighbors into consideration. ... In this model, we distinguish a node's direct neighbors from its neighbors' neighbors by giving different weights to them.

This section describes a K-SIP model where the weight information for an edge is defined as the times of the collaboration between the two authors.

And then, 10% of the original datasets is held out as test set and we run the Gibbs sampling process on the training set for i iteration. In particular, in generating the exemplary communities, we set the number of the communities as 50, the iteration times i as 1000. In perplexity computation, i is set as 300 in order to shorten the computation time. In both case, α is set as 1/K and β is set as 0.01, where K is the number of the communities.

Table III shows 6 exemplary communities from a 50-community solution for the CiteSeer dataset with social interaction profiles being created using 012-SIP representation. ...These exemplary communities give us some flavor on the communities that can be discovered by this approach. Specifically, we observe that some communities are “institution-based”, some others are “topic-based. ... This observation reveals the fact that researchers from same institution or with similar research interests tend to collaborate together more and build closer social ties.

Perplexity is is a common criterion for measuring the performance of statistical models in information theory. It indicates the uncertainty in predicting the occurrence of a particular social interaction given the parameter settings, and hence it reflects the ability of a model to generalize unseen data.

Perplexity PP is defined as

where w_m is the social interaction profiles in the test set and

where n^(v)_m is the number of times term t has been observed in document m.

It shows that the perplexity value is high initially and decreases when the number of communities increases. In addition, the results show that the 012-SIP approach has lower perplexity value than the other two approaches.

Compactness of a community is measured through the average shortest distance among the top-ranked N_r researchers in this community. Short average distance indicates a compact community.

The t-test results show that the 012-SIP approach is significantly better the other two approaches for both datasets

The probabilities that can be derived from SSN-LDA model can be helpful in determining the importance and roles of community members. For instance, the importance of community members conditioned on the community variable ι_j can be measured through the probability p(w_i|ι_j ), which can be easily derived from this model based on the learned ϕ.

SSN-LDA model provides an elegant way to measure the similarity of two communities by calculating the corresponding KL (Kullback-Leibler) distance and convert it to similarity measure. KL divergence is a distance measure for two distributions and the corresponding formula for calculating the distance between two communities ι_i and ι_j is:



This paper describes an LDA (latent Dirichlet Allocation)-based hierarchical Bayesian algorithm, namely SSN-LDA(Simple Social Network LDA). In SSN-LDA, communities are modeled as latent variables in the graphical models and defined as distributions over social actor space. The advantage of SSN-LDA is that it only requires topological information as input.

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.