Discussion Paper No. 97
Identifying Topic-based Communities
by Combining Social
Network Data and User Generated Content
Mirai Igarashi
Nobuhiko Terui

April, 2019

 Data Science and Service Research
Discussion Paper

Center for Data Science and Service Research
Graduate School of Economic and Management

Tohoku University27-1 Kawauchi, Aobaku

Sendai 980-8576, JAPANIdentifying Topic-based Communities by Combining Social
Network Data and User Generated Content
Mirai Igarashi∗

Nobuhiko Terui∗April, 2019∗
Mirai Igarashi is Doctoral student, Tohoku University, Graduate School of Economics and Management,
Kawauchi Aoba-ku, Sendai, 980-8576, Japan (E-mail: mirai.igarashi.s7@dc.tohoku.ac.jp). Igarashi acknowledges a grant by JSPS KAKENHI 18J20698. Nobuhiko Terui is Professor, Tohoku University, Graduate Schoolof Economics and Management (E-mail: terui@econ.tohoku.ac.jp). Terui acknowledges a grant by JSPS KAKENHI (A) 17H01001.

1

Identifying Topic-based Communities by Combining Social
Network Data and User Generated Content
Abstract
This study proposes a model for identifying communities by combining two types of
data: social network data and user-generated-content (UGC). The existing models for
detecting the community structure of a network employ only network information. However, not all people connected in a network share the same interests. For instance, even if
students belong to the same community of “school,” they may have various hobbies suchas music, books, or sports. Hence, targeting various networks to identify communities
according to their interests uncovered by their communications on social media is more
realistic and beneﬁcial for companies. In addition, people may belong to multiple communities such as family, work, and online friends. Our model explores multiple overlapping
communities according to their topics identiﬁed using two types of data jointly. By wayof validating the main features of the proposed model, our simulation study shows thatthe model correctly identiﬁes the community structure that could not be found without
considering both network data and UGC. Furthermore, an empirical analysis using Twitter data clariﬁes that our model can ﬁnd realistic and meaningful community structuresfrom large social networks and has a good predictive performance.

Keyword: Social network analysis, Community detection, User-generated-content, Topic
modeling, Bayesian inference2

1

Introduction
The product or information diﬀusion is aﬀected by not only the communication between

companies and consumers but also by interactions between consumers such as word-of-mouth
on social media or product reviews on e-commerce sites; the impact of the latter is stronger
in the modern social media development. Companies are required to implement various
marketing activities considering such relationships between consumers. A signiﬁcant ﬁrst
step towards learning about the relationship between customers is to grasp the community
structure of their social networks. If nodes of a network can be divided into some (potentiallyoverlapping) groups such that nodes are densely connected internally, the network is said tohave a community structure. Furthermore, researchers know that social network structureswith closely connected nodes, or consumers, can bring some beneﬁts to companies such as
sharing contents (Peng et al, 2018), achieving long-term popularity (Ansari et al, 2018), andaccelerating product innovation (Peres, 2014). Therefore, grasping the community structureof the customers’ social networks may prove to be useful for companies when planning theirmarketing activities.
A lot of attention has been paid to identifying community structures for a long time,and many methods have been proposed (e.g., Newman, 2006; Ng, Jordan, & Weiss, 2002;
Nowicki & Snijders, 2001; Handcock, Raftery, & Tantrum, 2007). In addition to social network
analysis, these methods are used in many other ﬁelds, including analysis of protein-protein
interaction networks (Jeong et al, 2001), terrorists networks (Krebs, 2002), and co-author
networks (Liu et al, 2005).
However, these methods focus only on network information, while more meaningful communities could be identiﬁed if other social network information was considered. For example,
students belonging to the same community of “school” are thought to be connected to eachother via some types of relationships to form social networks. Such networks are regarded as
one community when considering only network information. At the same time, the students
may be involved in various hobbies such as music, books, or sports. More meaningful segmentation can be achieved if researchers regard networks whose members have diﬀerent properties(or interests) as multiple communities rather than one. To do so, text information on social

3

media representing user-generated-content (UGC) and uncovering members’ interests can beused. Employing both the network and text information can allow researchers to recognize
the community structure from two viewpoints: the density of the network connections andsimilarity of interests derived from text information.
To understand the community structure of a social network, the problem of people belonging to multiple communities such as family, work, and online friends should be consideredin addition to network data and UGC. This problem is called community overlapping. The
estimated network structure in this case can have a large deviation from that of the real
network when applying methods such as hard clustering, where each node in considered tobelong to a single community. The mixed membership stochastic block model (MMSB) proposed by Airoldi, Fienberg, & Xing (2008) is one of the most popular statistical generativemodels investing the community overlapping problem. In this study, we extend MMSB andpropose a model, called the mixed membership stochastic topic block model (MMSTB), for
identifying communities by combining social network data and UGC.
The rest of this paper is organized as follows: related work is discussed in Section 2. The
proposed model, MMSTB, and its inference algorithm are introduced in Section 3. Section
4 examines the simulation studies conducted to validate the main features of MMSTB andchoose numbers of communities and topics. Section 5 presents an application of the proposedmodel to a real-world network, namely, Twitter. Finally, Section 6 provides some concluding
remarks.

2

Literature review

2.1

Social networks and consumer behavior

Many studies have focused on the impact of the structure of a social network on consumer
behavior (see Muller & Peres, 2018, for a comprehensive review). As a remarkable achievementof these studies, researchers know that consumers belonging to the same community positively
inﬂuence each other’s consumption behavior. For example, Peng et al (2018) used the content
shared on Twitter and found that a receiver is more likely to share content from a sender withwhom they have more common followers, common followees, and common mutual followers.
4Peres (2014) demonstrated that the higher the average degree a network has, the faster the
product innovation progresses; that is, consumption behaviors are more active in the network.
People belonging to the same community tend to have many common acquaintances becauseof the high density of connections; hence, they are likely to be more intimate. Based on theseresults, it is sensible for companies to grasp the groups (or communities) of customers who
have positive inﬂuences on each other’s consumption behavior.

2.2

Identifying communities using network information

A number of models have been proposed in the literature to identify the community
structure of a network. They can be divided into approaches using deterministic algorithm
and statistical models. One of the approaches using a deterministic algorithm is based on themodularity score introduced by Newman (2006), where modularity is a measure of the strengthof connections within a network divided into modules; a network with high modularity forms
dense connections between the nodes within modules but sparse connections between nodes
in diﬀerent modules. The algorithm proposed by Newman (2006) detects communities by
maximizing modularity, and this algorithm is one of the most widely used methods due
to its simplicity. Another approach using a deterministic algorithm is spectral clustering(Ng, Jordan, & Weiss, 2002), which is based on the eigenvalue decomposition of the graphLaplacian. The graph Laplacian is a matrix obtained by transforming the adjacency matrix,
and the community structure can be clariﬁed by applying some clustering methods such as
k-means for the eigenvectors of the graph Laplacian.
The community detection methods using statistical models have been well developed inpast decades, with the representative one being the stochastic block model (SBM) proposedby Wang & Wong (1987) and formulated by Snijders & Nowicki (1997) and Nowicki & Snijders (2001). The SBM assumes that when the cluster membership of each node is given, therelationship between nodes is generated according to some probability distribution such as the
Bernoulli distribution. Many researchers have studied the statistical properties of the SBM(e.g., Sussman et al, 2012; Abbe, 2018) and proposed extended models (e.g., Karrer & Newman, 2011). Another statistical model for detecting community is the latent position clustermodel (LPCM, Handcock, Raftery, & Tantrum, 2007) that extends the latent space model
5

(LSM, Hoﬀ, Raftery, & Handcock, 2002). While the LSM models the edge probability using
a parameter representing the latent position of a node, the LPCM introduces the hierarchicalstructure of the spherical Gaussian mixture model for the latent position parameter. The
spherical Gaussian distribution corresponds to the latent position of the community to which
nodes belong on their social network, and hence, the LPCM allows identifying the community
structures.
Recently, some models have been proposed to accommodate community overlapping (Gormley & Murphy, 2010; Latouche, Birmele, & Ambroisé, 2011; McDaid & Hurley, 2010). In
particular, the MMSB (Airoldi et al, 2008) allows each node to belong to multiple clusters byextending the SBM, which imposes the constraint that nodes can belong to only one cluster.

2.3

Simultaneous modeling of network Data and user-generated-content

The models introduced in Section 2.2 consider only network information (i.e., the connections between nodes). Conversely, simultaneously modeling network data and UGC for a
deep understanding of modern social networks such as Twitter and Facebook would be useful,because the pieces of information allows researchers to recognize a social network structurethat is more valuable for companies by accommodating the detection of heterogeneous relationships and interests across a speciﬁc community that are hidden in social network data.
For instance, it is possible that there is a group of music lovers in a community of school.
Several studies on the community identiﬁcation considering network data and UGC (particularly text) have been developed recently. In an earlier study, Zhou et al (2006) proposed
the community user topic model (CUT). The CUT extends the latent Dirichlet allocation(LDA, Blei, Ng, & Jordan, 2003) model for natural language processing to accommodate
the phenomenon that users with the same interests, that is, those who create texts with thesame topic, tend to belong to the same community. However, people who belong to the samecommunity do not necessarily create texts with the same topic, and the CUT can only clarify
a limited community structure of a social network.
Pathak et al (2006) proposed the community author recipient topic (CART) model thatincorporates both network and text information to extract well-connected and topically meaningful communities. Furthermore, CART allows the nodes to belong to multiple communities.
6

Conversely, the CART assumes textual edges, where text information appertains to edges,
which is the case in e-mail networks and co-authorship networks of papers and is diﬀerent
from the focus of this research. In addition, unlike the CART designed only for directed
graphs, our model can handle both directed and undirected graphs.
Liu et al (2009) proposed the topic-link LDA (TL-LDA) method that detects the community structure by considering information in a situation with textual nodes, which is similar
to our research; however, this method assumes that each node has a single community membership. In addition, the probability of creating an edge between nodes is deﬁned by thesimilarity of the community and topic proportion of the nodes. Hence, the probability isconstant regardless of the direction of the edge and can be applied to undirected graphs only.
In a recent study, Bouveyron, Latouche, & Zreik (2018) proposed the stochastic block
topic model (STBM) that extends the SBM by incorporating text information into the modeland is suitable for both undirected and directed graphs. If a node belongs to community A
and another node belongs to community B, the SBM handles any graph regardless of whether
it is directed or not by estimating the probability separately for the cases of generating edges
from A to B and from B to A. While our proposed method can handle the two types of graphs
similar to the STBM, our method also overcomes the limitation of the STBM, where nodes
can have only a single community membership.
Finally, we clarify the characteristics of our model. Table 1 summarizes the discussed
models compared by ﬁve characteristics. When comparing to the models that consider either
network or text information only (such as LDA, SBM, and MMSB), our model has an advantage of being able to extract well-connected topically meaningful communities by taking
both types of information into account. When comparing to the models that consider bothtypes of information, our model can be distinguished from the existing models according to
the following three properties: nodes can have multiple community memberships; graphs canbe both directed and undirected; text information appertains to nodes, which is the situation,
where people send their own tweets to all users on their Twitter timeline. Considering thesefeatures, we call our model the MMSTB.

7

Table 1: Comparison between the proposed model and existing models
Mixed
Direction Situation
Network Text
membershipof graphof text
LDA×
(Blei, Ng, & Jordan 2003)
SBM

×
×
Both
(Nowichi & Snijders, 2001)
MMSB

×

Both
(Airoldi et al., 2008)
CUT
Only
Textual(Zhou et al., 2006)
directededges
Only
Textual
CART(Pathak et al., 2006)
directededges
TL-LDA
Only
Textual×(Liu et al., 2009)
undirected
nodes
STBM
Textual×Both(Bouveyron et al., 2018)
edges
MMSTB
TextualBoth(This study)
nodes

3

Model
This section describes the proposed model MMSTB for community identiﬁcation. Our

observed data consist of the adjacency matrix A as a network information and bag-of-words
collection W as a text information. In the following, we explain the process of generatingthese data and inference procedure employed in MMSTB.

3.1

Model speciﬁcation

First, we consider a directed network with D nodes. D × D adjacency matrix A represents
the relationships between the nodes with their elements being aij = 0 (not connected) or 1(connected). We assume that the network has no self-loops and therefore aii = 0, ∀i. For the
relationship from node i to node j, we consider that sender i belongs to latent community sij ∈{1, . . . , K} (K is the number of communities), while recipient j belongs to latent communityrji ∈ {1, . . . , K}. D×D matrix representations of latent communities are denoted as S = (sij )and R = (rji ), respectively. These sender and recipient communities are assumed to follow

8a categorical distribution, sij |ηi ∼ Categorical(ηi ), rji |ηj ∼ Categorical(ηj ), where ηi =(ηi1 , . . . , ηiK )T is a community distribution which represents node i’s community proportion,
and K
k=1 ηik = 1, ∀i. The matrix representation of community proportions are denoted as
H = (η1 , . . . , ηD ). The prior distribution of H is assumed to follow a Dirichlet distribution,
ηi |γ ∼ Dirichlet(γ) (i = 1, . . . , D), where γ = (γ1 , . . . , γK ) is a hyperparameter.
We assume that the connection variable aij between node i to j, when sij and rji are
given, follows the Bernoulli distribution that depends on the community of the nodes. Thatis, aij |sij , rji , Ψ ∼ Bernoulli ψsij ,rji , where ψkk is a probability that an edge is generated
when a sender node belongs to community k and a recipient node belongs to community k  .
Let K × K matrix, Ψ = (ψkk ) be the matrix representation of edge probabilities. Each edge
probability is assumed to follow a Beta distribution, ψkk |δkk , kk ∼ Beta(δkk , kk ) (k, k  =1, . . . , K), where δ,  are hyperparameters of the K × K matrix.
Then, the conditional joint likelihood of the network information for parameters and latentvariables, when the community distribution, H, is given, isp(A, S, R, Ψ|H) = p(A|S, R, Ψ)p(S|H)p(R|H)p(Ψ|δ, )
⎫
⎧
D ⎨ 
D
⎬

{p(aij |sij , rji , Ψ)p(sij |ηi )p(rji |ηj )} ×⎭⎩
i=1

j=1,j=iKK 

p(ψkk |δkk , kk ),(1)

k=1 k =1

where δ and  are hyperparameters for Ψ and ﬁxed to some values.
For UGC, this study considers text data such as contents created by people on social
media or blogs. However, other types of UGC (e.g., images, movies, or music) can also be
handled by MMSTB after appropriate modeling.
Next, we consider modeling text content. Node i creates some texts that are vectorized as
Mi words ignoring the order, i.e., “bag-of-words”. Node i’s mth word wim (m = 1, . . . , Mi )is assumed to have latent community xim ∈ {1, . . . , K} and latent topic zim ∈ {1, . . . , L}
(L is the number of topics), as in the case of the conventional LDA model. The array
representations of words, word communities, and word topics are denoted as W , X, and Z,

9respectively, and each component of the arrays is a Mi -dimensional vector. We assume thatword community xim follows a categorical distribution, xim |ηi ∼ Categorical(ηi ). We notethat ηi is a parameter for generating not only word community xim but also node communities
sij and rij as mentioned before, that is, ηi is a common parameter for modeling networks andtexts that connects the two types of information.
A word topic zim is assumed to follow a categorical distribution, zim |xim , Θ ∼ Categorical(θxim ),where θk = (θk1 , . . . , θkL )T is the topic distribution representing community k’s topic proporLtion, andl=1 θkl = 1, ∀k. The matrix representations of topic proportions are denotedas Θ = (θ1 , . . . , θK ). Each topic distribution is assumed to follow a Dirichlet distribution,
θk |α ∼ Dirichlet(α) (k = 1, . . . , K), where α = (α1 , . . . , αL ) is a hyperparameter.
When a word topic zim is given, the corresponding word wim ∈ {1, . . . , V } is assumed tofollow a categorical distribution that depends on word topic, i.e., wim |zim , Φ ∼ Categorical(φzim ),where φl = (φl1 , . . . , φlV )T (V is the number of unique words in the corpus) is the word distribution representing the word generation probability, and Vv=1 φlv = 1, ∀l. The matrix
representation of word distributions is denoted as Φ = (φ1 , . . . , φL ). Each word distribution
is assumed to follow a Dirichlet distribution, φl |β ∼ Dirichlet(β) (l = 1, . . . , L), where β is a
hyperparameter.
Then, the conditional joint likelihood of text information, when H is given, isp(W, X, Z, Θ, Φ|H) = p(W |Z, Φ)p(Z|X, Θ)p(X|H)p(Θ|α)p(Φ|β)
D


Mi


i=1
K


m=1

k=1

{p(wim |zim , Φ)p(zim |xim , Θ)p(xim |ηi )} ×p(θk |α)Lp(φl |β),

(2)

l=1

where α and β are hyperparameters for Θ and Φ, respectively, and these are ﬁxed to somevalues. Under the assumption of conditional independence of Equations (1) and (2), whennodes’ community distribution, H, is given, the full joint likelihood of MMSTB is obtained10

by the product of Equations (1) and (2) multiplied by the density of H, p(H|γ),p(A, W, S, R, X, Z, H, Ψ, Θ, Φ)
⎧
D ⎨ 
D

=
{p(aij |sij , rji , Ψ)p(sij |ηi )p(rji |ηj )} ×⎩
i=1

j=1,j=iMi{p(wim |zim , Φ)P (zim |xim , Θ)p(xim |ηi )} ×

m=1
D

i=1

p(ηi |γ)K
k=1

p(θk |α)Kp(ψkk |δkk , kk )

k =1

×

L


p(φl |β).

(3)

l=1

The corresponding graphical model is provided in the left panel of Figure 1, while theright panel shows the model overview when K = 3 and L = 3. This illustrates the generative
process of the relationship between node i and j, aij , and the mth word of the text createdby node i, wim . A sender community sij (orange) and a recipient community rji (blue) are
generated according to their community distributions with parameters ηi and ηj , respectively.
Then the link probability, p(aij = 1|sij , rji , Ψ), is denoted as ψsij ,rji , which is an (sij , rji )element of the edge probability matrix Ψ. Conversely, a word community xim (orange) is
also generated according to the same distribution with parameter ηi . Then, a word topic zim(yellow) is generated according to topic distribution with θ2 corresponding to xim . Finally, aword wim is generated according to word distribution φ1 because zim equals to 1 (yellow).

3.2

Conditional posterior distributions and parameter estimation

Many methods for estimating topic models have been proposed (e.g., the variational
Bayesian method and sequential learning method). Among them, the most widely usedmethod is the collapsed Gibbs sampler (CGS) proposed by Griﬃths & Steyvers (2004), whichsamples only latent variables by integrating out parameters. CGS can estimate topic models
more eﬃciently compared to the Gibbs sampler that directly samples all parameters. This
study uses CGS for estimating MMSTB’s parameters.
MMSTB has four types of model parameters: namely, community distributions H, edge
probabilities Ψ, topic distributions Θ, and word distributions Φ. First, we derive the conditional posterior distributions from the full joint distribution according to Equation (3) by11dŽƉŝĐŝƐƚƌŝďƵƚŝŽŶ

ߛ

ߙ

‫ݎ‬

‫ݏ‬
ܽ

‫ܦ‬

ߠ

ߟ

ߟ

‫ݔ‬

߰
ߜ

߳

‫ݎ‬௝௜

‫ܭ‬

ߠଷ

‫ݖ‬௜௠

tŽƌĚƐŽĨEŽĚĞ݅‫ݏ‬௜௝ ܽ௜௝ߟ௜‫ݔ‬௜௠ ‫ݓ‬௜௠tŽƌĚŝƐƚƌŝďƵƚŝŽŶ

͙‫ܯ‬௜ ‫ܦ‬ĚŐĞ WƌŽďĂďŝůŝƚǇ

߶
‫ܭ‬ଶ

ߠଶ

ߠଵ

ŽŵŵƵŶŝƚǇ
ŝƐƚƌŝďƵƚŝŽŶ

‫ݖ‬
‫ݓ‬

ߟ௝

ĚũĂĐĞŶĐǇDĂƚƌŝǆ

ZĞůĂƚŝŽŶƐŚŝƉܽ௜௝ ‫ א‬ሼͲǡ ͳሽ

‫ܮ‬

tŽƌĚ

‫ݓ‬௜௠ ‫ א‬ሼͳǡ ǥ ǡ ܸሽ

̱

ߚ

̱

߶ଵ

͙
߶ଶ

߰

͙
߶ଷ

Figure 1: Graphical representation of the mixed membership stochastic block model (left)
and the model overview when the number of community (K) is 3 and the number of topics(L) is 3 (right)

using the conjugacy, Dirichlet-Categorical relationship for H, Θ, and Φ and Beta-Bernoulli
relationship for Ψ. Then, the full conditional posterior distributions, when data (A, W ), thestate of latent variables (S, R, X, Z), and hyperparameters are given, can be easily derived
as follows:Γ(P (ηi |S, R, X, γ) = k Nik + Mik + γk )k Γ(Nik + Mik + γk )KNik +Mik +γk
ηik

k=1
(+)
(−)
Γ(nkk + nkk + δkk + kk ) I(aij =1)ψkk
(1 − ψkk )I(aij =0)
P (ψkk |A, S, R, δ, ) =(+)(−)Γ(nkk + δkk )Γ(nkk + kk )LΓ ( l Mkl + αl )  Mkl +αl
P (θk |X, Z, α) =θklΠl Γ(Mkl + αl )l=1VΓ ( v Mlv + βv )  Mlv +βv
P (φl |W, Z, β) =φlv,
Πv Γ(Mlv + βv )

(4)

(5)

(6)

(7)

v=1

where Nik is the count number of when node i is assigned community k on the edges fromnode i to other nodes and from other nodes to node i. Mik is the count number of when
(+)

(−)

words in node i’s document are assigned to community k. nkk (nkk ) is the number of links

12(non-links) from nodes in community k to nodes in community k  . Mkl is the count numberof when words are assigned to community k and topic l. Mlv is the count number of whenword v is assigned to topic l. Γ is the gamma function, and I is the indicator function that
returns 1, if the condition is satisﬁed, and 0 otherwise.
MMSTB has four types of latent variables: two latent variables for a relationship between
node i and j, sij (sender community) and rji (recipient community), and two latent variables
for a mth word of node i, xim (word community) and zim (word topic). The conditional
posterior distributions of these four latent variables are derived by integrating out parameters(H, Ψ, Θ, Φ) as follows:
P (sij = k, rji = k  |aij , A\ij , S\ij , R\ji , X, γ, δ, ) ∝
P (sij = k|ηi )P (rji = k  |ηj )P (xi |ηi )P (xj |ηj )
ηi



ηj

P (ηi |S\ij , R\ji , X, γ)P (ηj |S\ij , R\ji , X, γ)dηi dηj ×ψkk

P (aij |ψkk )P (ψkk |A\ij , S\ij , R\ji , δ, )dψkk

Nik\ij + Mik + γk
Njk \ji + Mjk + γk
× 
×
= 
t Nit\ij + Mit + γtt Njt\ji + Mjt + γtI(aij =1) I(aij =0)

(+)
(−)
nkk \ij + kk
nkk \ij + δkk
(+)

(−)

(8)

nkk \ij + nkk \ij + δkk + kk

P (xim = k, zim = l|wim = v, W\im , S, R, X\im , Z\im , α, β, γ)∝P (si |ηi )P (ri |ηi )P (xim = k|ηi )P (ηi |S, R, X\im , γ)dηi ×ηiP (zim = l|θk )P (θk |X\im , Z\,im , α)dθk × θkP (wim = v|φl )P (φl |W\im , Z\im , β)dφlφlMkl\im + αlNik + Mik\im + γk
Mlv\im + βv
× 
× 
,
= 
u Mlu\im + βu
q Mkq\im + αqt Nit + Mit\im + γt(9)where the symbol \ represents the exclusion of an edge or a word from the count number.
The algorithm of CGS for MMSTB is provided in the Appendix 1. In CGS, according to13

Equations (8) and (9), the latent community and topic for each edge and word are sampled G
times. Finally, using the samples of the latent variables excluding the burn-in samples beforeb, model parameters are estimated as follows;
G
(g)
(g)
Nik + Mik + γk
1 η̂ik =
(g)(g)
G
N +M +γ
g=b+1

ψ̂kk =

θ̂kl =

t

it

it

G
(+,g)
nkk + δkk
1 
(+,g)
(−,g)
G
g=b+1 nkk + nkk + δkk + kk

(11)

G
(g)
Mkl + αl
1 



(g)
G
M +α

(12)

g=b+1

q

kl

q

G


(g)
Mlv + βv1.
φ̂lv =

(g)
G
+
β
M
u
g=b+1
u
lu

4

(10)

t

(13)

Numerical experiments
This section described the numerical experiments we conducted to highlight the mainfeatures of the proposed approach and provide the validity of our inference algorithm.

4.1

Experimental settings

The main features of our modeling are the mixed membership of nodes and simultaneous modeling of network data and text content. The characteristic of a mixed membership
captures the situation of people belonging to multiple communities on a social network andbuilding relationships with other members of these communities. Furthermore, extracting
more meaningful segments from social networks by considering both network data and text
content is possible.
To highlight these two properties of MMSTB, we have designed three diﬀerent scenarios. Table 2 provides the settings of each scenario, while Figure 2 depicts an example of
the generated adjacency matrix, where black (white) cells mean the presence (absence) of a
relationship between two nodes. We set some values for the community distribution, edge
probability, and topic distribution but did not set any values for the word distribution. Instead, for all scenarios, 150 words are sampled per node according to their word topics from14

the BBC news document dataset (Greene & Cunningham 2006) as virtual text contents; thisdataset contains three topics: namely, business, entertainment, and sports.
Scenario A
The network and text content are composed of K = 3 communities and L = 2 topics.
Each node belongs to only one community (Node 1-20, 41-60, 81-100) or two communities (Node 21-40, 61-80); that is, these communities are overlapping. But the edge
probabilities across the communities are lower (ψkk = 0.1) than within the communities (ψkk = 0.5), and each community has a unique topic proportion (θ1 = θ2 = θ3 ).
Therefore, both MMSTB and other models using only one source of information suchas LDA and MMSB can be expected to detect these communities accurately.
Scenario B
Similar to scenario A, each node belongs to one or two communities, and K = 4 communities are overlapping. Unlike scenario A, the community 1 and 4 have the same
topic proportions (θ1 = θ4 ). Therefore, the models using only text content information
cannot distinguish between the nodes that belong to only community 1 (Node 1-20) or
community 4 (Node 91-100). Conversely, the edge probabilities across the communities
are low; hence, both MMSTB and models using only network information should be
able to distinguish all communities.
Scenario C
The community 1 and 4 have the same topic proportion, and the text content-basedmodels cannot distinguish between these two communities. Furthermore, the edge probabilities between communities 3 and 4 (ψ34 , ψ43 ) are high; that is, people in these communities are well-connected even if they have diﬀerent interests (topics). Therefore, thenetwork-based models cannot identify these two communities. Only MMSTB can detect
all communities and recover the community structure properly.
We note that nodes are divided into some clusters where they belong to the same community (communities) with the same proportion and generate virtual texts of the same topic(s).
Each row of H in Table 2 corresponds to each cluster, and, for example, in scenario A, nodes
1-20 are classiﬁed into the same cluster. Whether models can recover these cluster structures
15

Table 2: The settings of three simulation scenarios (see text for details)
Scenario
D (nodes)K (communities)
L (topics)

A
100
3
2
{η1 , . . . , η20 } : (1, 0, 0){η21 , . . . , η40 } : (.5, .5, 0){η41 , . . . , η60 } : (0, 1, 0){η61 , . . . , η80 } : (0, .5, .5){η81 , . . . , η100 } : (0, 0, 1)

Community dist.
H

Topic dist.
Θθ1 = (1, 0)
θ2 = (.5, .5)
θ3 = (0, 1)

Edge prob.
Ψψ11 , ψ22 , ψ33 = .5
otherwise .1

B
100
4
2
{η1 , . . . , η20 } : (1, 0, 0, 0){η21 , . . . , η40 } : (.5, .5, 0, 0){η41 , . . . , η60 } : (0, 1, 0, 0){η61 , . . . , η80 } : (0, .5, .5, 0){η81 , . . . , η90 } : (0, 0, 1, 0){η91 , . . . , η100 } : (0, 0, 0, 1)
θ1 = (1, 0)
θ2 = (.5, .5)
θ3 = (0, 1)
θ4 = (1, 0)
ψ11 , ψ22 , ψ33 , ψ44 = .5
otherwise .1

C
100
4
3
{η1 , . . . , η20 } : (1, 0, 0, 0){η21 , . . . , η40 } : (.5, .5, 0, 0){η41 , . . . , η60 } : (0, 1, 0, 0){η61 , . . . , η80 } : (0, .5, .5, 0){η81 , . . . , η90 } : (0, 0, 1, 0){η91 , . . . , η100 } : (0, 0, 0, 1)
θ1 = (.5, 0, .5)
θ2 = (.5, .5, 0)
θ3 = (0, 1, 0)
θ4 = (.5, 0, .5)
ψ11 , ψ22 , ψ33 , ψ34 , ψ43 , ψ44 = .5
otherwise .1

40

40

40

Sender20

Sender20

Sender

20

60

60

60

80

80

80

20

40

60

80

20

40

60

80

20

40

60

Recipient
Dimensions: 100 x 100

Recipient
Dimensions: 100 x 100

Recipient
Dimensions: 100 x 100

Scenario A

Scenario B

Scenario C

80

Figure 2: Adjacency matrix for each scenario; the black cells represent the link presence,
whereas the white cells represent the link absence

depends on the situation of each scenario as described above. In the next section, we validate
whether our model and the models that are popular in the literature, namely, LDA as a textbased model and MMSB as a network-based model, are able to correctly estimate parameters
and identify true cluster structures.

4.2

Reproducibility of parameters and recovery of cluster structures

This section presents the experiments we conducted to verify whether the considered
models (LDA, MMSB, and MMSTB) can reproduce parameters and recover cluster structures
as described in the previous section. The modeling assumptions for LDA and MMSB are16

taken from the original papers (Blei, Ng, & Jordan, 2003 and Airoldi et al, 2008), while thegenerative process of these models is outlined in the Appendix 2. As LDA is a model for text
content and MMSB is a model for network data, we provide only text data of the simulated
dataset for LDA, only network data for MMSB, and the entire dataset for MMSTB. Similar to
MMSTB, we use CGS to estimate parameters of LDA and MMSB. The number of iterations
is set to 5,000, and the ﬁrst 2,000 samples are excluded as burn-in samples. The values of thehyperparameters for the respective prior distributions are listed in Table 3.
First, we carry out an experiment to verify the reproducibility of parameters. Figure 3
and Table 4 show the results of scenario C estimating MMSTB. The three panels in Figure
3 show the estimated parameters, community distribution (left), edge probability (top-right),
and topic distribution (right-bottom). The results show that MMSTB reproduces the values
provided in Table 2 with high accuracy. Table 4 lists the top 10 words for each topic indescending order of the estimated word distribution values. From left to right, words related
to business, entertainment, and sports are lined up, which implies that MMSTB extracts all
topics correctly. Therefore, MMSTB behaves appropriately when detecting more meaningfulcommunities by allowing nodes to have mixed memberships and considering network data andtext content simultaneously. The results of the other scenarios and models are provided in
the Appendix 2.
Next, we conducted an experiment to demonstrate the recovery of cluster structures fromthe simulated dataset. These cluster structures can be found using the estimated node-speciﬁcparameters. In particular, MMSB and MMSTB have a node-speciﬁc community distribution,
whereas LDA has a node-speciﬁc topic distribution. For example, MMSTB’s community
distribution aﬀects the generation of both the network and text data as explained in Section
3, while the nodes having similar values for the node-speciﬁc parameter (e.g., nodes 1-20 inscenario A have the same value for community distribution) should generate similar networkand text data. Therefore, it is natural that these nodes are classiﬁed into the same cluster.
In this experiment, we apply a clustering method, spectral clustering (Ng, Jordan, & Weiss,
2002), to the estimated node-speciﬁc parameter of each model and compare the clusteringresults with the true labels listed in Table 2.
The process of the experiment is as follows. First, we simulate datasets for each scenario17according to Table 2. Second, we estimate the model parameters while providing text data for
LDA, network data for MMSB, and both datasets for MMSTB. The number of iterations andhyperparameter values are the same as described above. Next, we classify nodes according
to the estimated node-speciﬁc parameters using spectral clustering (Ng, Jordan, & Weiss,
2002) 1 . Then, we calculate the adjusted Rand index (ARI, Hubert & Arabie, 1985) between
the cluster and true labels, with higher ARIs representing higher similarity between theselabels (when the labels perfectly match, ARI is 1). Because spectral clustering employs the
k-means method, its result depends on the initial value of the number of clusters. Hence, we
independently calculate ARIs for 20 diﬀerent initial values of the the number of clusters andset the latter according to the obtained maximum ARI value. Finally, we repeat this process
50 times with the diﬀerent seed value when generating datasets but the same parametersettings (Table 2).
Table 5 lists the medians of 50 ARIs calculated for the three models and three scenarios.
According to the result of scenario A (ﬁrst column), all medians of ARIs are 1.0; that is, allmodels can recover the true clusters. This result can be explained by the fact that the links
within (between) communities are dense (sparse) while the topics of texts within a community
are distinct from that of other communities. Even if only network data or text information
are employed, diﬀerences between clusters can be identiﬁed.
According to the result of scenario B (second column), ARIs of MMSB and MMSTB are
1.0, whereas LDA’s ARI is lower than before. In scenario B, community 1, to which nodes
1-20 (cluster 1) belong, and community 4, to which nodes 91-100 (cluster 6) belong, have thesame value of the topic proportion; therefore, these clusters cannot be distinguished whenlooking at text data only. Conversely, non-diagonal elements of the edge probability are low;that is, the diﬀerence between these clusters is clear when considering network data. This is
the reason why MMSB and MMSTB are able to recover the true clusters.
Finally, according to the result of scenario C, ARI is 1.0 only for MMSTB, whereas the
ARI values of LDA and MMSB are far less than 1.0; that is, the latter models are unable tocorrectly cluster nodes. The reason for this result is that the text data in scenario C havethe same topic structures as that of scenario B (topic distributions of communities 1 and 4
1

The algorithm for spectral clustering we use is implemented as a function “specc” in R-package “‘kernlab”.

18

Table 3: The setting of hyperparameters for the simulation experiments
Hyperparameters
γ
δ

α
β
Prior distributions ηi ∼ Dir(γ) ψkk ∼ Beta(δkk , kk ) θk ∼ Dir(α) φl ∼ Dir(β)γk = 1.0,δkk = 0.1, kk = 0.1,
αl = 0.1,
βv = 0.1,
Value∀k∀k, k ∀k, k ∀l∀v

Table 4: Top 10 words in descending order of the word distribution for each topic
Topic 1
Topic 2
Topic 3
(Business) (Entertainment)(Sports)bankﬁlm
champion
growth
award
cup
oil
actor
coach
proﬁt
album
rugbi
euro
nomin
irelandstock
bandseasonyuko
song
injuriinvestor
oscar
olymp
award
chart
championshipdeﬁcitactressgoal

are the same). Furthermore, the edge probabilities between communities 3 and 4 are equal
to the probabilities within these communities; that is, both communities completely overlap
in the network. Therefore, these communities cannot be identiﬁed when considering network
data only. On the other hand, MMSTB takes both network and text data into account andhence is able to recover the true cluster structures. This numerical experiment reveals thatour proposed model can correctly identify structures of communities and topics even if thesestructures overlap, which is one of the most notable features of our model.

Table 5: Medians of the adjusted Rand indices for the clustering result using the estimatednode-speciﬁc parameters of the three models (LDA, MMSB, and proposed model) in the three
scenarios
Scenario A Scenario B Scenario C
LDA
1.0
0.85
0.85
MMSB
1.0
1.0
0.93
MMSTB
1.0
1.0
1.0

19

Community distribution
1

2

3

4

5

6

Edge probability
7

8

9

10
4

21

31

12

22

32

13

23

33

14

24

34

15

25

35

16

26

36

17

27

37

18

28

38

19

29

39

20

Sender community

11

30

40

42

43

44

45

46

47

48

49

3

0

0.5

0 0.510.54

0.4
0.3

2

0.01 0.5 0

0

0.5 0

0

0

3

4

0.2
0.1

50
1

2

Recipient community
51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

Topic distribution

4

0.52

0

0.48
value

71

72

73

74

75

76

77

78

79

CommunityValue

0 0.5 0.47
value

1
41

0

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

1234 1234 1234 1234 1234 1234 1234 1234 1234 1234

Community

3

0

1

0

0.50
2

0.5 0.5

0

1

0.5

0

0.5

2

3

1

Topic

Figure 3: The estimation results of scenario C (see text for details)

20

0.75

0.25

4.3

Choosing the number of communities and the number of topics

The numbers of communities K and topics L need to be ﬁxed before applying SBM or
one of its extended models (DCSB, MMSB, MMSTB, etc.). A variety of approaches has
been proposed in the literature for choosing these numbers, including information criteriasuch as BIC (Handcock, Raftery, & Tantrum, 2007; Saldana, Yu, & Feng, 2017), integrated
completed likelihood (Daubin, Picard, & Robin, 2008; Bouveyron, Latouche, & Zreik, 2018),
cross-validation (Chen & Lei, 2018), and Bayesian inference (Latouche, Birmele, & Ambroise,
2012; McDaid et al., 2013).
In this study, the numbers of communities and topics are determined using an information criteria based on its solid theoretical ground and convenience of calculating from theoutputs of CGS. However, the topic models (including MMSTB), which have latent variables,
are known as singular models, and information criteria for regular models such as AIC and
BIC are not appropriate. Therefore, we employ the widely applicable information criterion(WAIC, Watanabe 2010) because it can be applied to both regular and singular models.
WAIC estimates the expected pointwise predictive density for a new dataset. It is deﬁned
as −2(lppd − pwaic ), where lppd denotes the log pointwise predictive density representing thepredictive accuracy of the ﬁtted model to data, and pwaic denotes a term to correct for bias
due to overﬁtting2 . The deﬁnition of WAIC for MMSTB is provided in the Appendix 3.
In addition to the reproducibility of MMSTB parameters of described above, we conﬁrm
that the numbers of communities and topics can be correctly estimated by the model selection
using WAIC. The procedure of the model selection simulation is as follows. For each scenario,
we generate simulation data according to the values listed in Table 2. We estimate the models
within the range of numbers of communities and topics from 2 to 6, and the model with thesmallest WAIC is selected. The results of repeating these procedures 50 times are shown in
Table 6. In all three scenarios, the model selection using WAIC succeeds in identifying thecorrect combination of the numbers of communities and topics. These experiments allow us
to validate WAIC as a model selection criterion for MMSTB.

2
In this study, we use the Gelman et al (2013)’s scale with −2n times Watanabe’s original deﬁnition (n isthe number of data). This scale enables us to compare with other information criterion such as AIC and DIC

21

Table 6: The number of times WAIC selects each MMSTB model (K, L) in 50 simulations ofeach of the three scenarios

5

Empirical analysis

5.1

Dataset(K)

Scenario C (K = 4, L = 3)
Topics (L)
2 3 4 5 6
2 0 0 0 0 0
3 0 0 0 0 0
4 0 46 1 1 0
5 0 2 0 0 0
6 0 0 0 0 0

Communities(K)

Scenario B (K = 4, L = 2)
Topics (L)
2 3 4 5 6
2 0 0 0 0 0
3 0 0 0 0 0
4 38 1 0 0 0
5 11 0 0 0 0
6 0 0 0 0 0

Communities(K)

Communities

Scenario A (K = 3, L = 2)
Topics (L)
2 3 4 5 6
2 0 0 0 0 0
3 46 2 0 0 0
4 2 0 0 0 0
5 0 0 0 0 0
6 0 0 0 0 0

In this section, we apply our model to empirical data to demonstrate the usefulness of
MMSTB for actual social networks. In particular, we employ the Twitter platform and usergenerated text data collected by the authors. We focus on a Twitter ego network centered on
the oﬃcial account (@NintendoAmerica) operated by a subsidiary company of Nintendo Co.,
Ltd. in U.S., Nintendo of America Inc. We created a dataset for analysis according to thefollowing procedure.
First, users were randomly sampled from the users who follow the oﬃcial account ofNintendo of America based on the following-followed relationship on May 1, 2018. Next,
additional users were randomly sampled from the users who follow the users following theNintendo account. The users whose average of the numbers of followers and followees isless than 3 in this network were excluded as outliers (note that the numbers of followers andfollowees are the numbers in the dataset and not the actual numbers). As a result, the numberof selected users is 3,500, the number of total link edges are 68,949 (i.e., each user has 19.7
edges on average), and their directed relationships are used as network information.
Next, we collected the tweets posted by the selected users on their timelines from September 1, 2017 to February 28, 2018 3 . These tweet data were preprocessed as follows: decomposing into word sets for each user, changing to lowercase letters, excluding numbers, symbols,
3

We conﬁrmed that the majority of users posted about the presentation of a new game software, called
Nintendo Direct, in March 2018. Hence, in this study, to avoid the eﬀect of such text information commonly
posted by many users, we decided to limit the period of data to be until February 28, 2018.

22

(K)

Communities

Table 7: WAIC of each model of MMSTB estimated for the Twitter dataset (bold represents
the smallest value)
Topics (L)
5
6
7
8
9
10
5 4, 601, 682 4, 591, 215 4, 547, 102 4, 651, 380 4, 651, 888 4, 521, 875
6 4, 633, 828 4, 580, 391 4, 564, 193 4, 568, 752 4, 629, 114 5, 563, 824
7 4, 607, 615 4, 588, 504 4, 627, 986 4, 564, 135 4, 596, 299 4, 553, 339
8 4, 613, 074 4, 637, 185 4, 623, 877 4, 517, 891 4, 564, 046 4, 537, 160
9 4, 612, 382 4, 626, 961 4, 557, 745 4, 540, 766 4, 500, 094 4, 571, 307
10 4, 598, 036 4, 580, 622 4, 580, 856 4, 544, 071 4, 534, 666 6, 629, 801

and some popular stop-words (a, the, I, etc.) and reducing inﬂected words to their word
stem. Among the preprocessed words, we excluded those with low frequencies (words having
the number of occurrences in the corpus less than 20 or used by less than 20 users) or highfrequencies (words used by more than 50 users) because these words may adversely aﬀect the
topic extraction. Then, the users whose number of words is less than ﬁve are also excluded.
As a result, the number of unique words in the corpus is 9,001, and the average number ofwords per node is 98.2 (the average unique word number is 59.3). Next, we applied MMSTB
to this Twitter dataset. The model selected by WAIC was (K, L) = (9, 9) as shown in Table
7.

5.2

Empirical results

Because the considered dataset is a large-scale network, unlike the simulation network
described in the previous section, understanding the results of the model estimation is diﬃcult
even if we showed the community distributions of all nodes and the entire network image.
Therefore, we focus only on a certain node when discussing the results of this experiment.
Figure 5 illustrates a sub-network consisting of a speciﬁc node (node 95), its neighbors, andthe partial results of the estimated parameters related to them. Furthermore, Figure 4 shows
the top 10 words for each topic.
First, interpreting the meaning of each topic from the top 10 words is necessary to understand what kind of interest people in the community display. The meaning of topics andtheir related words are as follows:23

Topic 1
animation (e.g., blackclover, hunter×hunter, and jojos bizarre adventure are the titlesof animations);
Topic 2
game (e.g., steinsgate, xenovers, and acnl, Animal Crossing: New Leaf, are the titles ofgame software);
Topic 3e-sports (e.g., hori and mkleosaga are words related to ﬁghting-games, while wnf andmdva are e-sports speciﬁc words);
Topic 4music (e.g., vevo, spinrilla, and wshh are websites for music);
Topic 5everyday life (e.g., people post texts and images of their everyday life with the hashtagsof dogsoftwitter and momlife);
Topic 6 and 7
business (e.g., digitalmarket, socialmediamarket, and contentmarket are the hashtags
which are sometimes used in a business-related tweet);
Topic 8streaming and broadcasting (e.g., teamemmmmsi, twitchkitten, roku, and wizebot arewords related to streaming or broadcasting);
Topic 9sports (e.g., orton and sdlive, oiler, horford, and herewego are wrestling, ice hockey,
basketball, and american football speciﬁc words, respectively).
Based on the interpretation of the topics provided above, obtaining some interesting insights from the sub-network of node 95 is possible. In Figure 5, the pie-charts show the valuesof the node’s community distribution, ηi ; bar plots are the values of the community’s topic
distribution, θk ; and arrows represent that there is a following relationship between the nodes,
24where the start node of the arrow is a sender of the following, the end node of the arrow is arecipient of the following, while the bidirected arrow means the mutual-following relationship.
The interpretation of a huge network, such as these Twitter data, is hardly achievableeven if we looked at the entire network image. However, the local sub-network and the estimated parameters corresponding to them provide useful insights on not only the relationshipbetween nodes but also overlapping communities, their proportions of belonging communities,
and characteristic topics within each community. For instance, nodes 95 and 336 belong tocommunity 5, in which people often post sports-related tweets (Topic 9). Node 95 belongs to
not only community 5 but also community 1 related to music (Topic 4) together with othernodes (804, 2241, 3476). Thus, the communities detected by our model represent a subset
of nodes with not only dense links on the network but also similar topics in their texts. In
the ﬁeld of consumer behavior analysis, researchers know that product or information diffusion tends to become faster among people located in a well-connected area of their social
network (i.e., they belong to the same community) as discussed in Muller & Peres (2018). In
addition to the network eﬀect, people in the community identiﬁed by our model share theirinterests owing to the same topic of texts posted on Twitter. Therefore, our model can help
companies to detect some useful community structures that positively aﬀect the consumption
behaviors. By analyzing the relationship between a company’s followers and its created text
content using our model, marketing managers can understand community structures and theinterests of the customers connected through these communities. The managers can then use
the obtained knowledge to update their marketing strategies accordingly.

5.3

Predicting on holdout samples

In this section, we demonstrate the predictive performance of our model on some test data
generated by holding out a part of the dataset described in Section 5.1. Unlike the experiment
outlined in the previous section, where the entire dataset was used for the model estimation,
90% of edges of each node with D − 1 edges are selected randomly in this experiment and usedas training data, while the remaining 10% of edges are used as test data. For the text data,
all words of each node are selected as training data. The settings of the hyperparameters
are the same as listed in Table 3, and the numbers of communities and topics are ﬁxed at25

ƉŽĚĞƌŶĨĂŵŝůŝ

ǀŐĐ

ŚŽƌŝ

ǀĞǀŽ

ůĞĞĚ

ƚƌĂƉĂĚƌ

ŐƌŽǁƚŚŚĂĐŬ

ŶŽŶĨŽůůŽǁ

ǌĞůĚĂƚŚŽŶ

ŐĂŵĞĚĞƐŝŐŶ

ƐĂǀǀŝŵŬůĞŽƐĂŐĂ

ƐƉŝŶƌŝůůĂ

ĐƚŽĚŝŐŝƚĂůŵĂƌŬĞƚ

ŐĚƉƌƚĞĂŵĞŵŵŵŵƐŝ

ĚŽŬŬĂŶ

ĐƌŝƚŝĐĂůƌŽů

ŐĂŵĞĚĞƐŝŐŶ

ǁŶĨ

ůƵďĞ

ŵŽŵůŝĨ

ĚĚƌŝǀĞ

ƐŽĐŝĂůŵĞĚŝĂŵĂƌŬĞƚ

ƚǁŝƚĐŚŬŝƚƚĞŶ

ŚƚŐĂǁŵ

ďůĂĐŬĐůŽǀ

ƐƚĞŝŶƐŐĂƚ

ŵĚǀĂ

ƐƵĂǀ

ĚŽŐƐŽĨƚǁŝƚƚ

ĐŽŶƚĞŶƚŵĂƌŬĞƚ

ŝĂƌƚŐ

ƌŽŬƵ

ŽƌƚŽŶ

ŚƵŶƚĞƌǆŚƵŶƚĞƌ

ŶǇǆůŚǇƌƵůĞƐĂŐĂ

ĚƌŝƉƉŝŶ

ďĞĐŬ

Ɛŵŵ

Ɛŵŵ

ǁŝǌĞďŽƚ

ŽŝůĞƌũŽũŽƐďŝǌĂƌƌĞĂĚǀĞŶƚƵƌ

ǆĞŶŽǀĞƌƐ

ĐĨůĂŚƐĐƵůƚ

ĂƵƐƚƌŝĂ

ĂŵƌĞĂĚ

ŐĂŝŶǁŝƚŚƉǇĞǁĂǁ

ƌǇǌĞŶƐĚůŝǀĞ

ĨƵƌƐƵŝƚĨƌŝĚĂǇ

ĂĐŶů

ŶŽŽĚ

ǁƐŚŚ

ŚĞŵƉ

ďŝŐĚĂƚĂ

ĂƐŵƐŐĂŝƌĚƌŽƉ

ŚŽƌĨŽƌĚ

ƚĨĐĂƌƚƐƚĂƚ

ƋĂŶďĂ

ŽƵŝũĂ

ƚŽĐŬ

ŐĚƉƌ

ŝĨď

ĚŐ

ŚĞƌĞǁĞŐŽ

ĂŵŝŐĂ

ĨŝƌĞƌ

ǌĞŬƵ

ĨŽŽĚƉŽƌŶ

ĐƌŽǁĚĨŝƌ

ŐĂŝŶǁŝƚŚǆƚŝĂŶĚĞůĂ

ĚŝŐŝƚĂůŵĂƌŬĞƚ

ĨƌĞĞďŝĞĨƌŝĚĂǇ

ƌŽǌŝĞƌ

ƐŝǌǌůŵŽŶĂĐŽ

ĨŝǀĞƌƌ

ĐƐƐdŽƉŝĐϰdŽƉŝĐϱdŽƉŝĐϲdŽƉŝĐϳƐŵůdŽƉŝĐϭƚĂŵĂŐŽƚĐŚŝ ũƵŶĞĚĞĐĞŵď
dŽƉŝĐϮdŽƉŝĐϯƐƚƌĞĂŵĞƌƐĐŽŶŶĞĐƚ ĞĂƌŶŚŝƐƚŽƌŝ
dŽƉŝĐϴdŽƉŝĐϵFigure 4: Top 10 words in descending order of the word distribution for each topic of Twitterdata

the same values as memtioned in the previous section, (K, L) = (9, 9). Using these settings,
we estimate the model parameters using the training dataset. Let the estimated community
distributions and edge probabilities be Ĥ and Ψ̂. Then, the predicted probabilities for thetest data aij ∈ Atest can be calculated as follows:

P (aij = 1) =

K
K 


η̂ik η̂jk ψ̂kk .

(14)

k=1 k =1

First, to see the predictive performance of our model, we use the receiver operating characteristic (ROC) curve shown in Table 6. The ROC curve connects plots of the true positive
rate as the y-axis against the false positive rate as the x-axis when the cutoﬀ value varies. If
the ROC curve overlaps the line at 45 degrees, the model randomly predicts the test data.
When the ROC curve is above this line, the model splits two groups (link or non-link) moreclearly. Therefore, the area under the curve (AUC) shows the predictive performance. The
AUC of Figure 6 is 0.93, which means that MMSTB has a good predictive performance.
Next, we search the best cutoﬀ value based on the predictive performance of our model.
By determining some cutoﬀ value, we can predict labels of test edges (link or non-link). Our
network data are imbalanced having many non-link edges (about 99.4% of edges are non-link).

26

dŽƉŝĐϵϭϭdŽƉŝĐϰ

Ϭ͘ϱ

Ϭ͘ϱ

Ϭ

Ϭ

ŽŵŵƵŶŝƚǇϱŽŵŵƵŶŝƚǇϭ

ૡ૙૝

૜૜૟

ૢ૞
૚૟ૡ૜

૜૝ૠ૟

૛૛૝૚

ŽŵŵƵŶŝƚǇϵϭϬ͘ϱdŽƉŝĐϭdŽƉŝĐϮŽŵŵƵŶŝƚǇϮ
ϭ

Ϭ

Ϭ͘ϱ

dŽƉŝĐϲ dŽƉŝĐϳϬŽŵŵƵŶŝƚǇϭŽŵŵƵŶŝƚǇϮŽŵŵƵŶŝƚǇϯdŽƉŝĐϭdŽƉŝĐϮdŽƉŝĐϯŽŵŵƵŶŝƚǇϰŽŵŵƵŶŝƚǇϱŽŵŵƵŶŝƚǇϲdŽƉŝĐϰdŽƉŝĐϱdŽƉŝĐϲŽŵŵƵŶŝƚǇϳŽŵŵƵŶŝƚǇϴŽŵŵƵŶŝƚǇϵdŽƉŝĐϳdŽƉŝĐϴdŽƉŝĐϵFigure 5: Sub-network consisting of a speciﬁc node (node 95) and its neighbors, and the results
estimated by MMSTB. Circles represent nodes (numbers in circles are node indicators); arrows
represent that there is a following relationship between the nodes; pie-charts represent theestimated community distributions and surrounding bar-graphs represent the estimateed topic
distributions.

27

1.0
0.8
0.6
0.4

True positive rate

0.2
0.0
0.0

0.2

0.4

0.6

0.8

1.0

False positive rate

Figure 6: Receiver operating characteristic curve for test edge samples

Table 8: Confusion matrix when cutoﬀ is set to 0.088, where the Matthews correlation coefﬁcient is the highest
Prediction
Link Non-link
2,041
4,786
Link
Data
Non-link 7,079 1,211,094

Therefore, we employ the Matthews correlation coeﬃcient (MCC) to imply the correlationcoeﬃcient between the true class labels and predicted labels. Using the obtained predictedprobabilities as described above, the cutoﬀ value with the highest MCC of 0.254 is determined
to be 0.088. Table 8 represents the confusion matrix for the test data computed using this
cutoﬀ value. According to this confusion matrix, our model predicts not only non-link edges
with high accuracy but also link edges with more than 40% accuracy despite the diﬃculty ofpredicting correctly due to the imbalanced nature of the data (the class size of the link data
is much smaller than that of the non-link data). This result demonstrates that our model
performs well as a predictive model.

28

6Conclusion
This study proposed a model, called MMSTB, for identifying realistic and beneﬁcial com-munities based on not only the relationships within a social network but also interests of its
members reﬂected by UGC. The main features of MMSTB are (1) extracting communities
and topics considering network information, which represents the relationships between network nodes, and text information posted on social media, which uncovers people interests,(2) allowing each node to belong to multiple communities, which is called mixed membership,and (3) being applicable to both directed and undirected graphs.
The CGS was used for the model inference, and the numbers of communities and topics
were chosen according to WAIC. Numerical experiments using simulated data conﬁrmed theabove-mentioned model features and showed that the procedures of the model inference andmodel selection work properly. As an empirical application, we analyzed Twitter data andfound realistic and beneﬁcial community structures that could not be obtained unless both
network and text information were considered. Furthermore, the proposed model demonstrated a good predictive performance on holdout samples.
Further work may include the problem of node heterogeneity. SBM and other extended
models assume that all nodes belonging to the same community are homogeneous and edges
within or between communities are generated according to the corresponding community’sedge probability. However, in general social networks, a few hub nodes tend to have manyedges, while many other nodes tend to have a few edges, even if they belong to the samecommunity. This property is called scale-free. Ignoring this node heterogeneity may lead to a
deviation of model results from the real network structure. Krivitsky et al (2009) introduced
a parameter representing node heterogeneity for the edge generating part of the LSM. Karrer& Newman (2011) proposed an extended SBM that corrects the probability of generating anedge between a pair of nodes considering the node degrees to address the problem of node
heterogeneity. This problem cannot be avoided in social network analysis; hence, our model
also needs to be extended to solve the problem.

29

Appendix
Appendix 1: Algorithm of the collapsed Gibbs sampler (CGS) for the proposed model (MMSTB)In Section 3.2, we derived the posterior distributions of latent variables. CGS repeats
sampling according to Equations (8) and (9) and updates the allocation counters of latent
communities and topics. The pseudo algorithm of CGS for MMSTB is provided in algorithm
1.
Algorithm 1 collapsed Gibbs sampler for MMSTB
1: Assign randomly communities and topics to S, R, X, Z
2: for g = 1, . . . , G do
3:
for i = 1, . . . , D do
4:for j = 1, . . . , D do
(+)
(−)
5:
Set Nik\ij , Njk \ji , nkk \ij , nkk \ij
6:
7:
8:
9:
10:

(g)

(g)

Sample edge communities, sij , rji , from (8)
(+)

(−)

Update Nik , Njk , nkk , nkkend forfor m = 1, . . . , Mi do
Set Mik\im , Mkl\im , Mlv\im

(g)

(g)

Sample word community and word topic, xim , zim , from (9)12:Update Mik , Mkl , Mlv
13:
end for14:
end for
15: end for11:

Appendix 2: Supplementary results of numerical experiments
In this Appendix, we show the remaining results of the numerical experiments that could
not be explained in the Section 4.2 due to the limited space. Before listing the results, we
brieﬂy introduce two statistical models widely used in the literature: namely, latent Dirichlet
allocation (LDA) and mixed membership stochastic block model (MMSB).

30The generative model for LDA is as follows:
word topic

zim |θi ∼ Categorical(θi ),i = 1, . . . , D,

m = 1, . . . , Mi

word wim |zim , Φ ∼ Categorical(φzim ),i = 1, . . . , D,

topic distribution

θi |α ∼ Dirichlet(α),

i = 1, . . . , D

word distribution

φl |β ∼ Dirichlet(β),

l = 1, . . . , L.

m = 1, . . . , Mi

The generative model for MMSB is as follows:
sender community

sij |ηi ∼ Categorical(ηi ),i, j = 1, . . . , D

recipient communityrji |ηj ∼ Categorical(ηj ),i, j = 1, . . . , D

aij |sij , rji , Ψ ∼ Bernoulli(ψsij rji ),i, j = 1, . . . , D

edgecommunity distribution

ηi |γ ∼ Dirichlet(γ),

edge probability ψkk |δ,  ∼ Beta(δkk , kk  ),i = 1, . . . , Dk, k  = 1, . . . , K.

The parameters estimated by LDA, MMSB, and MMSTB for the dataset of the considered
three scenarios are shown in Figures 8-14 (the result of MMSTB for scenario C is describedin Section 4.2).

31

Community distribution

Edge probability

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

0

21

31

22

32

23

33

24

34

25

35

26

36

27

37

28

38

29

39

30

40

Sender community

3

43

44

45

46

47

48

49

0

2

0.49

0.4

0

0.3
0.2
0.1

0.52

0

0

1

2

3

50

Recipient community
51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

Topic distribution

3

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

Community

Value

42

value
0.5

1

41

0.01 0.56

0.5

0.5

1

0.50

1.0

0
1.5

2.0

Topic

Figure 7: Estimation results of scenario A by MMSTB

32

value

0.25

0.5

Community

1

0.75
2

1

123 123 123 123 123 123 123 123 123 1230

2.5

ValueCommunity distribution

1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

Community

Figure 8: Estimation results of scenario A by LDA

33

1

2

1

2

Community distribution
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

Edge probability
31

32

33

34

35

36

37

38

39

40

Value

41

51

42

52

43

53

44

54

45

55

46

56

47

57

48

58

49

59

50

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

Sender community

3

0

0

0.56

0.5
2

0

0.51

0

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

0.3
0.1

1

0.5

0

0

1

2

3

123 123 123 123 123 123 123 123 123 123

Community

Figure 9: Estimation results of scenario A by MMSB

34

0.4
0.2

Recipient community
81

value

Community distribution
1

2

3

4

5

6

Edge probability
7

8

9

10

0

4

21

31

12

22

32

13

23

33

14

24

34

15

25

35

16

26

36

17

27

37

18

28

38

19

29

39

20

Sender community

11

30

40

42

43

44

45

46

47

48

49

0

3

0.5

0 0.5 0.02

0.4
0.3

0 0.52 0

2

0

0.2
0.1

0.54 0 0.01 0

50
1

2

3

4

Recipient community
51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

Topic distribution

1

4

0
value

71

72

73

74

75

76

77

78

79

CommunityValue

0 0.54
value

1
41

0

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

1234 1234 1234 1234 1234 1234 1234 1234 1234 1234

Community

0

3

1

0.50
2

0.49

0.51

1

1

0

0.5

1.0

1.5

2.0

Topic

Figure 10: Estimation results of scenario B by MMSTB

35

0.75

0.25

2.5

ValueCommunity distribution

1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

Community

Figure 11: Estimation results of scenario B by LDA

36

1

2

1

2

Community distribution
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

Edge probability
31

32

33

34

35

36

37

38

39

40

Value

41

51

61

42

52

62

43

53

63

44

54

64

45

55

65

46

56

66

47

57

67

48

58

68

49

59

69

Sender community

4

50

60

72

73

74

75

76

77

78

79

3

0 0.530

0 0.5 0.01

2

0 0.53 000.52 0

0

0

3

4

1

2

Recipient community
81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

1234 1234 1234 1234 1234 1234 1234 1234 1234 1234

Community

Figure 12: The estimation results of scenario B by MMSB

37

0.5
0.4
0.3

70

80

0

value

1

71

0

0.2
0.1

ValueCommunity distribution
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

Community

Figure 13: Estimation results of scenario C by LDA

38

Community distribution
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

Edge probability
31

32

33

34

35

36

37

38

39

40

Value

41

51

61

42

52

62

43

53

63

44

54

64

45

55

65

46

56

66

47

57

67

48

58

68

49

59

69

Sender community

4

50

60

72

73

74

75

76

77

78

79

3

0 0.52

0 0.3 0.5 020.290.280.28 00.480.21 0
1

2

0

3

Recipient community
81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

1234 1234 1234 1234 1234 1234 1234 1234 1234 1234

Community

Figure 14: Estimation results of scenario C by MMSB

39

0.5
0.4
0.3

70

80

0

value

1

71

0

4

0.2
0.1

Appendix 3: Deﬁnition of WAIC for MMSTB
The deﬁnition of WAIC for MMSTB is as follows:
⎛

⎞⎞
Mi
D
G 






⎝log ⎝ 1
P aij |H (g) , Ψ(g)P wim |H (g) , Θ(g) , Φ(g) ⎠⎠
lpd =
(15)
G
m=1
i=1
g=b+1 j=1
⎛
⎛
⎞
⎛
Mi
D
G
D


2 
2



G
1
⎝
⎝
⎝
log P aij |H (g) , Ψ(g) +log P wim |H (g) , Θ(g) , Φ(g) ⎠Pwaic =
G−1 G
m=1
i=1
g=b+1 j=1⎛⎛⎞⎞2 ⎞⎞
Mi
G
D


 



1
⎝
−⎝
log P aij |H (g) , Ψ(g) +log P wim |H (g) , Θ(g) , Φ(g) ⎠⎠ ⎠⎠
G
D


⎛

g=b+1

m=1

j=1

(16)
W AIC = −2 (lpd − Pwaic ) ,

(17)





where P aij |H (g) , Ψ(g) and P wim |H (g) , Θ(g) , Φ(g) are the model likelihood conditioned
with the parameters estimated using samples at sth iteration
K
K 
 

(g)I(a =1)(g)
ηik · ηjk · ψkk ij· (1 − ψkk )(g)I(aij =0)
P aij |H (g) , Ψ(g) =P wim |H

(g)

,Θ

(g)

,Φ

(g)



(18)

k=1 k =1
L
K 

(g)
(g)
(g)
ηik · θkl · φlwim .
=k=1 l=1

40(19)

References[1] Abbe, E. (2017), “Community detection and stochastic block models: recent developments,” The Journal of Machine Learning Research, 18(1), 6446-6531.
[2] Airoldi, E. M., Blei, D. M., Fienberg, S. E., & Xing, E. P. (2008), “Mixed membershipstochastic blockmodels,” Journal of Machine Learning Research, 9(Sep), 1981-2014.
[3] Ansari, A., Stahl, F., Heitmann, M., & Bremer, L. (2018), “Building a social network forsuccess,” Journal of Marketing Research, 55(3), 321-338.
[4] Blei, D. M., Ng, A. Y., & Jordan, M. I. (2003), “Latent dirichlet allocation,” Journal of
Machine Learning Research, 3(Jan), 993-1022.
[5] Bouveyron, C., Latouche, P., & Zreik, R. (2018), “The stochastic topic block modelfor the clustering of vertices in networks with textual edges,” Statistics and Computing,28(1), 11-31.
[6] Chen, K., & Lei, J. (2018), “Network cross-validation for determining the number ofcommunities in network data,” Journal of the American Statistical Association, 113(521),
241-251.
[7] Daudin, J. J., Picard, F., & Robin, S. (2008), “A mixture model for random graphs,”
Statistics and Computing, 18(2), 173-183.
[8] Gelman, A., Stern, H. S., Carlin, J. B., Dunson, D. B., Vehtari, A., & Rubin, D. B.
(2013), “Bayesian data Analysis,” Chapman and Hall/CRC.
[9] Gormley, I. C., & Murphy, T. B. (2010), “A mixture of experts latent position clustermodel for social network data,” Statistical Methodology, 7(3), 385-405.
[10] Greene, D., & Cunningham, P. (2006, June), “Practical solutions to the problem of diagonal dominance in kernel document clustering,” In Proceedings of the 23rd International
Conference on Machine learning, 377-384.
[11] Griﬃths, T. L., & Steyvers, M. (2004), “Finding scientiﬁc topics,” Proceedings of the
National Academy of Sciences, 101(suppl 1), 5228-5235.
41

[12] Handcock, M. S., Raftery, A. E., & Tantrum, J. M. (2007), “Model-based clustering forsocial networks,” Journal of the Royal Statistical Society: Series A (Statistics in Society),
170(2), 301-354.
[13] Hoﬀ, P. D., Raftery, A. E., & Handcock, M. S. (2002), “Latent space approaches to social
network analysis,” Journal of the American Statistical Association, 97(460), 1090-1098.
[14] Hubert, L., & Arabie, P. (1985), “Comparing partitions,” Journal of Classiﬁcation, 2(1),
193-218.
[15] Jeong, H., Mason, S. P., Barabási, A. L., & Oltvai, Z. N. (2001), “Lethality and centrality
in protein networks,” Nature, 411(6833), 41.
[16] Karrer, B., & Newman, M. E. (2011), “Stochastic blockmodels and community structure
in networks,” Physical Review E, 83(1), 016107.
[17] Krebs, V. E. (2002), “Mapping networks of terrorist cells,” Connections, 24(3), 43-52.
[18] Krivitsky, P. N., Handcock, M. S., Raftery, A. E., & Hoﬀ, P. D. (2009), “Representing
degree distributions, clustering, and homophily in social networks with latent cluster
random eﬀects models,” Social Networks, 31(3), 204-213.
[19] Latouche, P., Birmelé, E., & Ambroise, C. (2011), “Overlapping stochastic block models
with application to the french political blogosphere,” The Annals of Applied Statistics,
5(1), 309-336.
[20] Latouche, P., Birmelé, E., & Ambroise, C. (2012), “Variational Bayesian inference andcomplexity control for stochastic block models,” Statistical Modelling, 12(1), 93-115.
[21] Liu, X., Bollen, J., Nelson, M. L., & Van de Sompel, H. (2005), “Co-authorship networks
in the digital library research community,” Information Processing & Management, 41(6),1462-1480.
[22] Liu, Y., Niculescu-Mizil, A., & Gryc, W. (2009, June), “Topic-link LDA: joint models of topic and author community,” In Proceedings of the 26th Annual International
Conference on Machine Learning, 665-672.
42

[23] McDaid, A., & Hurley, N. (2010, August), “Detecting highly overlapping communities
with model-based overlapping seed expansion,” In 2010 International Conference on
Advances in Social Networks Analysis and Mining, 112-119.
[24] McDaid, A. F., Murphy, T. B., Friel, N., & Hurley, N. J. (2013), “Improved Bayesian inference for the stochastic block model with application to large networks,” Computational
Statistics and Data Analysis, 60, 12-31.
[25] Muller, E., & Peres, R. (2018 online), “The eﬀect of social networks structure on innovation performance: A review and directions for research,” International Journal of
Research in Marketing.
[26] Newman, M. E. (2006), “Modularity and community structure in networks,” Proceedingsof the National Academy of Sciences, 103(23), 8577-8582.
[27] Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002), “On spectral clustering: Analysis and analgorithm.” In Advances in Neural Information Processing Systems, 849-856.
[28] Nowicki, K., & Snijders, T. A. B. (2001), “Estimation and prediction for stochastic
blockstructures,” Journal of the American Statistical Association, 96(455), 1077-1087.
[29] Pathak, N., DeLong, C., Banerjee, A., & Erickson, K. (2008, August), “Social topic
models for community extraction,” In The 2nd SNA-KDD Workshop, 8, 2008.
[30] Peng, J., Agarwal, A., Hosanagar, K., & Iyengar, R. (2018), “Network overlap andcontent sharing on social media platforms,” Journal of Marketing Research, 55(4), 571585.
[31] Peres, R. (2014), “The impact of network characteristics on the diﬀusion of innovations,”
Physica A: Statistical Mechanics and its Applications, 402, 330-343.
[32] Saldana, D. F., Yu, Y., & Feng, Y. (2017), “How many communities are there?,” Journalof Computational and Graphical Statistics, 26(1), 171-181.
[33] Schwarz, G. (1978), “Estimating the dimension of a model,” The Annals of statistics,
6(2), 461-464.
43

[34] Snijders, T. A., & Nowicki, K. (1997), “Estimation and prediction for stochastic blockmodels for graphs with latent block structure,” Journal of Classiﬁcation, 14(1), 75-100.
[35] Sussman, D. L., Tang, M., Fishkind, D. E., & Priebe, C. E. (2012), “A consistent adjacency spectral embedding for stochastic blockmodel graphs,” Journal of the American
Statistical Association, 107(499), 1119-1128.
[36] Wang, Y. J., & Wong, G. Y. (1987), “Stochastic blockmodels for directed graphs,” Journal of the American Statistical Association, 82(397), 8-19.
[37] Watanabe, S. (2010), “Asymptotic equivalence of Bayes cross validation and widely applicable information criterion in singular learning theory,” Journal of Machine Learning
Research, 11(Dec), 3571-3594.
[38] Xing, E. P., Fu, W., & Song, L. (2010), “A state-space mixed membership blockmodelfor dynamic network tomography,” The Annals of Applied Statistics, 4(2), 535-566.
[39] Zhou, D., Manavoglu, E., Li, J., Giles, C. L., & Zha, H. (2006, May), “Probabilistic models for discovering e-communities,” In Proceedings of the 15th International Conferenceon World Wide Web, 173-182.

44