General Generator for Attributed Graphs with
Community Structure
Seiji Maekawa1 , Jianpeng Zhang2,3 , George Fletcher2 , and Makoto Onizuka1
1

Osaka University, 1–5 Yamadaoka, Suita, Osaka, Japan{maekawa.seiji,onizuka}@ist.osaka-u.ac.jp
2
Eindhoven University of Technology, the Netherlands g.h.l.fletcher@tue.nl
3
National Digital Switching System Engineering & Technological R&D Center(NDSC), China zjp@ndsc.com.cn

Abstract. We propose acMark, a scalable and general generator for
attributed graphs with cluster labels, which has the following advantages:(i) users can flexibly control the separability of the clusters from theviewpoints of both the topology and the attributes of graphs; (ii) users
can precisely specify various distributions for node degrees, cluster sizes,
and attribute values; and, (iii) graph generation scales linearly to thenumber of edges of generated graphs. Through extensive experiments, wedemonstrate that acMark can generate large-scale graphs with controlledcharacteristics as needed by contemporary graph analytics researchers.
Keywords: graph generator · attributed graph · community structure· graph property · latent factors.

1

Introduction

Graph is a fundamental data structure consisting of nodes and their relationships. Graphs are ubiquitous in many application domains, such as web graph[7], social networks [8], protein complexes [6], traffic planning [9], computer vision [13], and gene expressions [3, 15]. Of the rich variety of graph analytics
methods, graph clustering is one of the most widely used techniques in the machine learning and data mining fields [25].
When we consider real world applications, a node usually has multiple attributes. For example, in a social network a person node may have “age” and“language” as attributes. Contemporary graph databases support attributedgraphs (also known as property graphs) [5] and there emerges many attributedgraph techniques for clustering and classification tasks [1, 12, 23, 27] and representation learning [11, 31].
Researchers often need large-scale attributed graphs with various characteristics and flexible community structure in order to experimentally validate
the effectiveness and efficiency of methods for such tasks. Although there aremany real world attributed graphs available in repositories, most of them do nothave cluster labels. Indeed, SNAP [19], which is the most widely known grapharchive, does not include any attributed graphs with cluster labels. We can find2

S. Maekawa et al.

attributed graphs with cluster labels in some graph research projects4 , however
most of them are small-scale graphs. Turning to large-scale and synthetic graphgeneration, the state of the art methods for attributed graphs with clusters can
not specify various types of distributions for node degree, cluster size, or attribute values [4, 17]. As an example, [17] does not allow the user to control the
distribution of cluster size and the attribute values. It only permits to use anormal distribution.
To address this need in the field, we propose acMark for generating largescale attributed graphs with controlled characteristics and flexible community
structure. The major strength of acMark is that it can flexibly control the separability of the clusters and specify various types of distribution for node degree,
cluster size, and attribute values. To the best of our knowledge, this is the firstgraph generator that can generate attributed graphs with flexible community
structure. The idea of acMark is that, it first generates intermediate data structures, the latent factors of clusters, and then generates attributed graphs byusing the latent factors. The latent factors are flexibly generated based on any
distributions specified by the user. acMark generates nodes by following the
proportions of the latent factors and then generates edges so as to satisfy the
topology property. acMark also controls the distribution of the cluster sizes andattribute values. For each node attribute, acMark generates a value by following
two rules: 1) if two nodes belong to the same cluster they should share similarvalues, and 2) the values should follow the distribution specified by the user.
acMark is efficient in that the graph generation scales linearly with the edge
size of the output graph. As a community resource, acMark is available as open
source code.5
Our contributions in this paper include a systematic presentation of acMark(Sections 2 and 3) and a detailed experimental analysis of the scalability andquality of generated graphs, including an application to clarifying the characteristics of existing clustering methods (Section 4). We also discuss related state of
the art methods (Section 5). We give concluding remarks in Section 6.

2

Preliminaries

An attributed graph is a triple G = (N, E, X) where N = {1, 2, . . . , n} is anode set, E = {(i, j)} ⊆ [n] × [n] is an edge set, and X : N → domX1 ×· · · × domXd is a function from a node to its d attribute values. The cluster
assignment list obtained from the graph topology and the attributes is expressedby C ∈ {1, ..., k1 }n and C X ∈ {1, ..., k2 }n , respectively. Note that current graphgenerators only consider C without using C X .
2.1

Graph properties

We highlight two properties that real world graphs typically have: topology
property and attribute property.
45

For example, https://linqs.soe.ucsc.edu
https://github.com/seijimaekawa/acMark

acMark: scalable generation of attributed graphs with communities

3

Topology property. Real world graphs have well-known topology properties[18, 22], which are desirable in synthetically generated graphs: 1) the node degrees follow a power-law distribution, and 2) the cluster sizes follow a power-law
distribution. In addition, from the topology aspect, one of the difficulties ingraph generation is that the output graph should satisfy the topology property
while insuring all the edges have two adjacent nodes.
Attribute property. There are two types of attributes, categorical type (e.g.
conference, university, city) and numerical type (e.g. price, timestamp). In real
datasets, it is well known that most numerical attributes follow a normal distribution or power-law distribution. So, graph generators should control the distribution type of attribute values.
Comparisons. State of the art graph generators, such as LFR [16] and ANC [17],generate graphs by specifying distributions so that they satisfy the above properties, but only with limited types of distribution. Table 1 shows the comparisonsof our acMark, LFR [16], and ANC [17].

Table 1: Comparisons of different graph generators. PL indicates a power law
distribution and ND indicates a normal distribution. Our method supports arbitrary distributions for the node degrees, the cluster sizes, and attribute values.
Actually, the distributions of power law, uniform, and normal are implemented.
N A indicates that there is no support for the property.
Generator
LFR [16]
ANC [17]
Our method3

Node degree
PLPL
arbitrary

Cluster sizePLNA
arbitrary

Attribute
NA
R(ND)
arbitrary

Complexity
O(m)
O(m)
O(m)

acMark: attributed graph generator with flexible
community structure

We next present acMark, our generator for attributed graphs with flexible community structure and real world graph properties. The idea of acMark is that,instead of generating attributed graphs directly, we first generate intermediate
data structures, the latent factors of clusters, so that we can flexibly generate
attributed graphs with cluster labels. The features of acMark are three-fold.
First, acMark treats the topology clusters and the attribute clusters independently and the output graphs are generated by assuming there is a complex
relationship between the topology clusters and the attribute clusters. For instance, the topology and the attributes usually have different number of clusters
and, moreover, a topology cluster may be affected by multiple attribute clusters with different weights. Therefore, acMark controls the cluster separability
by using topology cluster proportions and attribute cluster proportions and also
takes into account such relationship by introducing cluster transfer proportions

4

S. Maekawa et al.

between the topology cluster proportions and the attribute cluster proportions.
We call those three proportions the latent factors of clusters.
Second, acMark generates attributed graphs from the latent factors so thatthe generated graphs reflect the cluster proportions, and also the generated
graphs should satisfy the graph properties as we described in Section 2.
Finally, we design acMark to scale linearly to the number of edges of generated graphs in terms of the time and space complexities.
3.1

Generating Model

We explain the detailed design of acMark by using Figure 1, with parameters
given in Table 2. acMark generates output graphs with cluster labels by using
1, attribute cluster prolatent factors: topology cluster proportions U ∈ Rn×k+
d×k2
portions V ∈ R+ , and cluster transfer proportions H ∈ Rk+1 ×k2 between U
and V . The output graph is expressed with topology cluster assignment listC, adjacency matrix S, and attribute matrix X. Topology cluster assignment
list C is obtained from topology cluster proportions U by choosing the largest
proportion cluster for each node6 . Intuitively, adjacency matrix S and attribute
matrix X can be generated by U and V , respectively. But, we also use U and
H for generating X, so that we simulate the complex relationship between the
topology clusters and the attribute clusters.
The adjacency matrix generation is not obvious, because the output graphshould reflect the topology property while insuring all the edges have two adjacent nodes. Since deciding whether there exists a graph satisfying the give
topology property is NP-complete [2], acMark takes a greedy approach for graphgeneration as follows. We sample the candidate of generating edges so as to satisfy the node degree constraint, and then, compute the probability of the edge
existence from the latent factors. Finally, we use a Poisson distribution for confirming edges based on the probability. We also carefully design acMark so thatruntime scales linearly with the number of edges.
acMark supports various input parameters as shown in Table 2. The most basic parameters are the number of nodes and edges to generate, and the distributions of the node degrees, the cluster sizes7 , and the attribute values (continuousor discrete)8 . We normalize all attribute values to [0,1] without the loss of generality. The ratio of attributes whose values follow the distribution of Bernoulli,
power law, uniform, or normal is controlled by attber , attpow , attuni and attnor ,respectively.9
6

Similarly, attribute cluster assignment list C X is obtained from V .
As for the exponents, we choose typical values of real networks: 2 ≤ φd ≤ 3, 1 ≤ φc ≤2, where φd and φc are the parameters for node degree and cluster size, respectively.
8
Categorical attribute values can be encoded with binary representation.
9
As for the reminder part of the ratio, the attribute values are generated independently from the latent factors. In this case, the attribute values follow a randomly selected a distribution from bernoulli, power law, uniform, or normal distributions. The
distribution parameters ω, which consist of φatt min , φatt max , δatt , σatt min , σatt max ,are used for the reminder part.
7

acMark: scalable generation of attributed graphs with communities

5

Table 2: Description of the graph generator parameters. φ consists of
φd , φc , φV , φH , δ consists of δd , δc , δV , δH , and σ consists of σd , σc , σV , σH . The
subscripts of φ, δ, and σ indicate as follow: d represents node degree, c represents
cluster size, V represents attribute cluster proportions and H represents clustertransfer proportions.
Inputn, m, d ∈ N
k1 , k 2 ∈ N
α ∈ R+β ∈ R+γ ∈ R+
φ ∈ R4δ ∈ R4σ ∈ R4
fS , f X
r∈N
attber ∈ R
attpow ∈ R
attuni ∈ R
attnor ∈ R
ω ∈ R∗

Description
number of nodes, edges, attributes
number of clusters for topology, attributes
parameters for balancing inter-edges and intra-edges
parameters of separability for attribute cluster proportions
parameters of separability for cluster transfer proportions
parameters of exponent for power law distribution
widths of uniform distribution
deviations of normal distribution
transformation for adjacency matrix, attribute matrix
number of iterations for edge construction
ratio of attributes which takes discrete value
ratio of attributes which follow power law distributions
ratio of attributes which follow uniform distributions
ratio of attributes which follow normal distributions
parameters of random attributes

Algorithm Algorithm 1 describes the procedure of graph generation. It consists of two phases, latent factors generation phase and graph generation phase.
In the latent factors generation phase, three latent factors are generated by latent factor generation function (line 1,3,4). We take a Bayesian approach for thelatent factor generation described in Algorithm 2. We treat ξ as random variables and place a prior distribution over it. Let W be the output proportionsof the function. A distribution χ is specified by the user, either of power law,
uniform, or normal (line 1). We generate a dirichlet distribution ξ based on τ χwhere τ controls the effect of W ’s columns to the cluster proportions (line 2).
That is, W ’s columns are related with only few clusters when τ is small. We use
a multinomial distribution to produce the output proportion Wi for each row(line 3-5). We obtain the number of attributes for each distribution based on theratio attber , attpow , attuni and attnor given by the user (line 2 in Algorithm 1).
These values are then used as input to decide the size of V (line 3). In the graphgeneration phase, we generate the adjacency matrix S (line 8), attribute matrix
X (line 9), and cluster assignment list C (line 5-7). The cluster assignment isdecided by the largest entry in the cluster proportion U for each node (line 6).
Algorithm 3 describes how the adjacency matrix S is generated. The idea isthat we randomly generate candidate edges and then they are confirmed as realedges if they follow the expected degree proportion of their adjacent nodes. The
detail is as follows. The expected node degree proportions θ is derived from the

6

S. Maekawa et al.

information of distributions,graph sizes,
attribute dimension, etc
Input
Latent factors

U

fS

C

V

H
fX

Assignment

S

X

OutputAdjacency

AttributeFig. 1: Illustration of our proposal. Each row of U indicates a cluster proportionfor each node. Each row of V indicates a cluster proportion for each attribute.

distribution specified by the user (line 1). θ 0 is the actual node degrees of thegenerating graph. It is initialized as zeros (line 2) and its entries θi0 and θj0 are
incremented when a new edge (i, j) is confirmed to be real one (line 16). For
each node i, edges are iteratively generated based on the node degree proportion
θi by Candidate selection step (line 7-10) and Candidate confirmation step (line12-20). In Candidate selection step, a candidate edge is listed as a pair of i andrandomly chosen node j ∈ M (line 9). In Candidate confirmation step, if theactual node degrees of the adjacent nodes (i and j) of a candidate edge do notreach to the expected ones (θi0 and θj0 , line 13), the edge existence is decided byusing a Poisson distribution (line 14). Note there is a possibility that this loop
does not stop, because the adjacency matrix generation is a type of combinatorial
optimization problem. We take a greedy approach: we exit the loop at the userspecified r iterations (line 5)10 . It is our future work to guarantee the theoreticalquality bounds of the generated graphs.
Algorithm 4 describes how the attribute matrix X is generated. The output
X is obtained by concatenating X U HV and random matrix X ran (line 8): we use
X ran for the purpose of generating values independent from clusters. X U HV
is generated by fX (U , H, V ). That is, 1) we obtain base attribute vectors fornodes by computing the product of U , H, V so that two nodes in the samecluster (reflecting the effect of the topology and attributes) should share similarvalues, and then 2) we apply user-specified distribution to the base attribute
vectors so that the attribute values should follow the distribution (line 1).

10

Although we adjust the sum of all the node degrees in θ to be the number of edges m,some candidate edges may not be generated when the node degrees of the adjacentnodes exceeds the expected ones, so the actual number of the generated edges tends
to be smaller than the expected number of edges, m.

acMark: scalable generation of attributed graphs with communities

7

Algorithm 1 Graph generation
Require: n, m, d, k1 , k2 , α, β, γ, φ, δ, σ, fS , fX , r, attber , attpow , attuni , attnor , ωEnsure: adjacency matrix S, attribute matrix X, cluster assignment list C# Latent factors generation phase
1: U = latent factor generation(c, n, α, φ, δ, σ)
2: dber , dpow , duni , dnor ← int(d×attber ), int(d×attpow ), int(d×attuni ), int(d×attnor )3: V = latent factor generation(V ,dber + dpow + duni + dnor ,β, φ, δ, σ)
4: H = latent factor generation(H, k1 , γ, φ, δ, σ)# Graph generation phase
5: for i = 0 to n do
6:
Ci = argmax(Ui ) # cluster assignment
7: end for
8: S = adjacency matrix generation(U , H, V , r, fS )9: X = attribute matrix generation(U , H, V ,d − (dber + dpow + duni + dnor ), ω)

Algorithm 2 latent factor generation(type, size, τ, φ, δ, σ)
1: χ = chooseF rom(power
P law(φtype ), unif orm(δtype ), normal(σtype ))2: ξ = Dirichlet(τ χ/ χ)
3: for i = 1 to size do
4:
Wi = mutinomial(ξ)
5: end for
6: return W

Algorithm 3 adjacency matrix generation(U , H, V , r, fS )1: θ = chooseF rom(power law(φd ), unif orm(δd ), normal(σd ))2: θ 0 = [0]n3: for i = 1 to n do
4:
counter = 0
5:while counter < r and θi0 < θi do
6:# Candidate selection
7:
M = {}
8:for j = 1 toSθi do
9:
M = M Randint (1, n)
10:
end for11:# Candidate confirmation: (i,j) is a candidate edge
12:for j ∈ M do
13:
if Sij == 0 and θi0 < θi and θj0 < θj then14:
Sij = fS (U ) #e.g. P oisson(< Ui , Uj >))15:
if Sij > 0 then16:
Sji = Sij # since undirected graph17:(θi0 , θj0 ) = (θi0 + 1, θj0 + 1)
18:
end if19:
end if
20:
end for21:
counter = counter + 1
22:
end while
23: end for
24: return S

8S. Maekawa et al.

Algorithm 4 attribute matrix generation(U , H, V , dran , ω)
1: X U HV = fX (U , H, V ) (e.g. (power law, unif orm, normal)(U HV > ) for numerical values, and Bernoulli(U HV > ) for categorical values)
2: for j = 0 to dran do
3:
dist = RAN D(Bernoulli, powerlaw, unif orm, normal)
4:
for i = 0 to n do
ran
5:
Xij
= dist(ω)
6:
end for
7: end for
8: X = concatenation(X U HV , X ran )9: return X

Complexity We discuss the space/time complexities of acMark. As is typical in
network analytics, we focus on sparse graphs [22] as real-world graphs are often
sparse. On the sparse condition, the mean of the node degree can be treated asa constant, m ∝ n, so m is considered to be a much smaller value than n2 .
Space complexity. The largest concern is the adjacency matrix S since the sizeof S could be as large as n2 . Hence, we use sparse representation for S, suchas an adjacency list, with size O(m). The size of an attribute matrix X is nd.
We can omit the size of the latent factors because k1 , k2  n, d. Therefore, thespace complexity is O(m + nd),Time complexity. We analyze the time complexity of the latent factor generation, the adjacency matrix generation, and the attribute matrix generation, respectively. First, the complexity for generating the topology cluster proportions,the attribute cluster proportions, and cluster transfer proportions is O(nk1 +dk2 + k1 k2 ) based on their matrix sizes. Second, the adjacency matrix generation consists of the candidate selection step and the candidate confirmation
step. In the candidate selection step, candidates are chosen based on the nodedegree. In candidate confirmation step, we calculate the edge probability whose
complexity is O(k1 ). These two steps are executed for each node so they requireO(nk1 rθAvg ), where r is the number of iterations for edge generation. Further,r = c × k1 where c is constant and m = nθAvg , that is, the complexity becomesO(mk12 ). Finally, in the attribute matrix generation, the complexity is O(ndk)
where k = min(k1 , k2 ). Therefore, the total time complexity is O(mk12 + ndk).

4

Experiments

We next describe an experimental study of acMark. Our goal in the experiments
is to answer the following questions:
Q1 Does acMark support users to control the distributions of graph properties?
Q2 How well does acMark scale?
Q3 Does acMark support users to flexibly control the separability of clusters?

acMark: scalable generation of attributed graphs with communities

9

Q4 Can we use acMark to clarify the characteristics of contemporary clustering
methods?
We use a power law distribution (φd = 3, φc = 2) for node degrees and cluster
sizes as a default setting. acMark is implemented in Python3, and, as noted in
Section 1, is made available as open source. The experiments are operated on 64
Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz with 32GB memory.
4.1

Q1: Visualization with controlled graph properties

To confirm that acMark supports the control of the distributions of graph properties, we visualize the distributions of the generated graphs.
Graphs with various topology properties. We visualize the generated graphswith various cluster sizes (Figure 2) and with various node degrees (Figure 3a, 3c)11 .
Figure 3b, 3d depict the histograms of the node degree distributions. These figures indicate that the generated graphs follow the graph properties specified by
the user.

(a) The cluster sizes follow a power law dis- (b) The cluster sizes follow a normal distribution (φc = 2).
tribution (σc = 0.1).

Fig. 2: Visualization of graphs with two different cluster size distributions generated by acMark. The node colors represent clusters. These graphs have 1000
nodes and about 4000 edges. The node degrees follow a power law distribution(φd = 3).

Graphs with various attribute properties. We analyze the attribute values
in the generated graphs. Figure 4 depicts the histograms of a single attributeand 2-D plots of the values of two attributes. Figure 4a, 4b depict the statistics
of attribute values that are generated without specifying distributions. Figure 4a
indicates that the values are clearly separated into clusters and we clearly observebase attribute vectors in Figure 4b. In contrast, Figure 4c, 4d depict the resultswith specifying a normal distribution to the attribute values. We observe thatthe values actually follow a normal distribution.
11

We utilize Gephi for the visualization. Note: Gephi is limited to place the vertices
based only on the graph topology and ignores the effect of the attributes.

10

S. Maekawa et al.

0.10
count

count

0.2

0.05
0.00 00.0

20
degree510degree(a) The node degrees(b) The node degree (c) The node degrees (d) The node degree
follow a power law
distribution of (a). follow a normal dis- distribution of (c).
distribution (φd =tribution (σd = 0.1).
3).

Fig. 3: Visualization of graphs with two node degree distributions generated byacMark. The node colors represent clusters. These graphs have 1000 nodes andabout 4000 edges. The cluster sizes follow a power law distribution (φc = 2).

count

2

0.5
0.0

0 0.0
0.00 0.25 0.50 0.75 1.00
attribute1

0.5
attribute value

1.0

attribute2

0.5
1.0
attribute value

attribute2

count

5
0 0.0

1.0

1.0

10

0.5
0.0

0.00 0.25 0.50 0.75 1.00
attribute1(c) Histogram of at(a) Histogram of at(b) Attribute values tribute values gener- (d) Attribute values
tribute values generof (a) plotted in 2-D ated by a normal dis- of (c) plotted in 2-D
ated without specispace.
space.
tribution.
fying distributions.

Fig. 4: Histograms and 2-D plots of attribute values. These graphs have 1000
nodes and about 4000 edges. The cluster sizes follow a power law distribution(φc = 2). In Figure 4c, 4d, mean = 1 and deviation is randomly chosen fromthe range of 0.1 – 0.3.

4.2

Q2: Scalability of graph generation

To investigate the scalability of acMark, we demonstrate how the runtime andmemory consumption vary for various values of parameters. The default settingof the parameters is as follows: d = 100, k1 = 10, k2 = 10, α = 1/k1 , σd =0.1, σc = 0.1, r = 10 ∗ k1 , attber = 0.0, attpow = 0.4, attuni = 0.1, attnor = 0.4. m
is chosen from {104 , 105 , 106 , 107 } and n = m/10 for keeping the sparse conditionof generating graphs. Figure 5a indicates that the runtime actually scales linearly
to the number of edges. The memory size of S also scales linearly to the numberof edges in Figure 5b. Figure 5c indicates that the number of the actual edges issmaller than the input parameter m: this result follows the discussion we madein footnote 8. As a whole, these experiments demonstrate that both time andspace complexities are linear to m, the number of edges.

1
0
0.0
0.5
1.0
m (number of edges(ideal)) [M](a) Runtime.

75
50
25
0
0.00 0.25 0.50 0.75
m (number of edges(ideal)) [M](b) Size of S.

number ofedges(actual) [M]2size of S [MB]runtime [K sec]

acMark: scalable generation of attributed graphs with communities

11

0.75
0.50
0.25
0.00
0.0
0.5
1.0
m (number of edges(ideal)) [M](c) Comparison with m andthe actual number of edges.

Fig. 5: Scalability experiments against the number of edges. The other parameters are set as follow: n = m/10, d = 100, k1 = 10, k2 = 10.

4.3

Q3: Separability of clusters

We next study the extent to which acMark supports flexible control of the separability of clusters in terms of the topology and the attributes. First, we visualize
the topology structure with various values of α and the attribute values withvarious combinations of β and γ. Second, we investigate structural measureswith various graph sizes and with various values of α.
Visualization. Figure 6 shows that the ratio of intra-edges is large when α
is small. This is one of the features of dirichlet distribution: clusters are more
separated if α is set at a smaller value. We also conduct experiments for β and(a) α = 1.0.

(b) α = 0.1

Fig. 6: Separability of clusters w.r.t. the topology when n = 1000, m = 4000, k1 =5. The node colors represent the clusters.
γ. Fig 7 shows how those parameters can control the separability of attributes.
The clusters are more overlapped when β and γ are set at larger values (SeeFig 7(a)) by following the feature of dirichlet distribution.
Structural measures. We investigate how modularity [21], average cluster coefficient, and graph diameter12 vary with various values of α. These measures
are often used to clarify the characteristics of graphs. Modularity is a measure
12

Diameters can not be calculated in unconnected graphs so we use the largest diameter
among connected components as the diameter of the whole graph.

12

S. Maekawa et al.
1.0

attribute2

attribute2

attribute2

0.5

0.5

0.5
0.0

1.0

1.0

0.0

0.5
attribute1

0.0

1.0

(a) β = 100, γ = 100.

0.0

0.5
attribute1

0.0

1.0

(b) β = 10, γ = 10.

0.0

0.5
attribute1

1.0(c) β = 1, γ = 1

Fig. 7: Separability of clusters w.r.t. attributes when n = 1000, k1 = 5. The nodecolors represent the clusters.
for topology: the score is high when clusters are separated with each other.
Figure 8 shows the average and deviation of the measures, where m is chosen from {5000, 10000, 15000, 20000}, n is fixed at 1000, and α is chosen from
{0.1, 0.2, 0.3}. For all measures, the scores tend to be large when α is small, thatis, separability is high. Graphs with high separability have obviously separated
clusters so modularity should be high. The separated clusters consist of densely
connected edges and, in this case, the average cluster co-efficient is high. As
for the diameter, the small value of α causes fewer number of inter-edges, so
the diameter becomes large when α is small. Overall, these results validate that
acMark flexibly controls the separability of clusters.
alpha=0.3

0.5
10000 15000
number of edges(a) Modularity

20000

alpha=0.3

8

0.2
0.1
5000

alpha=0.1
alpha=0.2

alpha=0.3

diameter

0.6

0.4
5000

alpha=0.1
alpha=0.2
cluster co-efficientmodularity

alpha=0.1
alpha=0.2

10000 15000
number of edges

20000(b) Cluster co-efficient

7
6
5
5000

10000 15000
number of edges

20000(c) Diameter

Fig. 8: Modularity, average cluster co-efficient, and diameter with various numbers of edges and various values of α. The number of nodes is fixed at 1000. The
bars around the points (average) represent the standard deviations of five trials.

4.4

Q4: Applying clustering methods to generated graphs

Finally, we show that acMark can clarify the characteristics of clustering methods. We apply three types of clustering methods to generated graphs, an attributed graph clustering method which captures both effects of the topology and attributes (NAGC [20]), a topology-based graph clustering method(METIS [14]), and an attribute-based clustering method (kmeans).
We adopt several measures for evaluating clustering methods, modularity,
entropy, NMI (Normalized Mutual Information), and ARI (Adjusted Rand Index) [29]. Entropy is a well-known measure for the diversity of attribute values.

acMark: scalable generation of attributed graphs with communities

13

NMI and ARI are popular measures for evaluating clustering quality with cluster
labels.
The input parameters of the datasets we generated are described in Table 3.
The results of the clustering methods may depend on initial values so we conduct
five restarts for each experiment. We report the results of the average and thestandard deviations.
Table 3: Generated datasets and their input parameters for the clustering experiments
ID
acMark1
acMark2
acMark3

n
1000
1000
1000

m
4000
4000
4000

d
10
10
10

k1
5
5
5

k2
5
5
5

α
0.2
0.2
0.1

β
10
10
10

γ
1
1
1

attpow
0.0
0.1
0.1

attuni0.0
0.1
0.1

attnor0.9
0.1
0.1

Table 4 shows the clustering quality of the methods. The true clusters ofacMark1 should highly depend on the attributes since most of the attributes
follow normal distributions (See high value in attnor column). The results showthat NAGC and kmeans perform better than METIS in terms of NMI and ARI,so acMark clarifies these methods take the effect of the attribute values into
community structure. Many attributes are independent from the community
structure in acMark2 and acMark3 since 70% (= 1 - attpow - attuni - attnor ) of
those attributes are randomly generated. Therefore, on acMark2, the attributes
are less dependent on the community structure than on acMark1. The result of
NAGC is kept high in terms of NMI and ARI while the result of kmeans largely
descends. This implies that NAGC well captures both effects of the topology
and the attributes. On acMark3, the clusters are more separated than acMark2
because the separability parameter α is smaller. Actually, the measurements ofall methods are better than those on acMark2.
According to these results, we confirm that acMark controls the characteristics of generated graphs and it is useful to clarify the characteristics of clustering
methods.

5

Related work

There is a rich literature on graph generation (e.g., [2, 10, 18]). In this section
we review the most closely related methods to our proposal.
Generator for graphs with community structure. The GN-benchmark [10]is the first graph generator for evaluating community mining algorithms. It only
supports 128 nodes and four groups. The LFR-benchmark [16] is the expansion of the GN-benchmark and it is a scalable graph generator. It assumes thatthe distributions of node degrees and community sizes should follow power-law

14

S. Maekawa et al.

Table 4: The average and standard deviation (in parenthesis) of clustering quality. Oracle represents the evaluation by using the ground truth.
DatasetMethodNMI
ARI
Modularity
Entropy
acMark1
Oracle 1.000(0.000) 1.000(0.000) 0.571(0.030) −0.787(0.045)
m = 4000
NAGC 0.751(0.000) 0.805(0.002) 0.579(0.000) −0.622(0.000)
α = 0.2
METIS 0.553(0.043) 0.512(0.060) 0.534(0.033) −0.588(0.068)
attnor = 0.9 kmeans 0.620(0.028) 0.547(0.041) 0.348(0.048) −0.768(0.062)
acMark2
Oracle 1.000(0.000) 1.000(0.000) 0.495(0.094) −0.450(0.147)
m = 4000
NAGC 0.662(0.008) 0.741(0.001) 0.524(0.002) −0.320(0.006)
α = 0.2
METIS 0.475(0.080) 0.393(0.135) 0.497(0.046) −0.268(0.085)
attnor = 0.1 kmeans 0.321(0.063) 0.209(0.056) 0.167(0.026) −0.394(0.047)
acMark3
Oracle 1.000(0.000) 1.000(0.000) 0.653(0.021) −0.412(0.048)
m = 4000
NAGC 0.834(0.014) 0.890(0.010) 0.599(0.005) −0.321(0.008)
α = 0.1
METIS 0.669(0.044) 0.606(0.053) 0.611(0.030) −0.290(0.046)
attnor = 0.1 kmeans 0.406(0.099) 0.278(0.088) 0.182(0.052) −0.346(0.063)

distributions. It is extended to generate synthetic graphs with overlapping communities [26] and hierarchical communities [28]. However, they do not support
node attributes.
Generator for graphs with community structure and node attributes.
There are few generators which take both community structure and node attributes into account. ANC [17] is a generator for attributed graphs with community structure. However, the community structure of generated graphs only
depends on the attributes, so the user can not explicitly control community
sizes and the effect of the topology to community structure. ANC is extended
to generate dynamic graphs [4], it generates dynamic attributed networks with
community structure, which follow the properties of real-world networks.
Recent graph generators. Although many graph generation methods havebeen developed, they are not capable of preserving important properties in realworld graphs. Also, they are not suitable for generating large-scale graphs due totheir large space and time complexities. In order to preserve multiple propertiesof real-world graphs, there are two recent work as follows.
GraphRNN. Jiaxuan et al. [30] propose GraphRNN that captures the non-uniquenature and the non-local dependencies in real world graphs. GraphRNN uses
a scalable generative model for generating graphs. That is, GraphRNN learns
how to generate graphs by training a representative set of graphs by leveraging
RNN and generates graphs. The drawback is that it does not generate arbitrary
graphs by controlling the types of distributions and also it does not directly treat
community structure.
EvoGraph. Himchan et al. [24] presents EvoGraph, which is capable of upscaling
given graphs, while preserving the major properties of the original graphs. The
rationale of EvoGraph is that new edges are generated and attached to theacMark: scalable generation of attributed graphs with communities

15

original graph based on the preferential attachment mechanism in an effective
and efficient way. However, an original graph is required as an input, so it ishard to control the graph properties as the user needs.

6

Concluding remarks

We proposed acMark, a scalable and general generator for attributed graphs withflexible community structure. The novel features of our method are threefold: 1)
acMark flexibly controls the cluster separability between the topology and theattributes, 2) acMark supports various distributions for node degrees, cluster
sizes and attribute values, and 3) acMark is a scalable generator: it scales linearly
to the number of edges. We conducted extensive experiments which confirm thesefeatures. Throughout the experiments, we validated that acMark can generatemassive graphs with various characteristics as the user wants.
Interesting directions for future work include extending acMark to generate
directed graphs, overlapping communities, and hierarchical communities. Also
it is an interesting topic to consider the graph generation problem as an inverseof graph clustering problem. We can design a single framework that treats both
directions of the graph generation and graph clustering.

References
1. Akoglu, L., Tong, H., Meeder, B., Faloutsos, C.: Pics: Parameter-free identificationof cohesive subgroups in large attributed graphs. In: Proceedings of ICDM. pp.
439–450 (2012)
2. Bagan, G., Bonifati, A., Ciucanu, R., Fletcher, G., Lemay, A., Advokaat, N.:
gMark: Schema-driven generation of graphs and queries. IEEE Trans. Knowl. Data
Eng. 29(4), 856–869 (2017)
3. Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. Journalof computational biology 6(3-4), 281–297 (1999)
4. Benyahia, O., Largeron, C., Jeudy, B., Zaı̈ane, O.R.: Dancer: Dynamic attributed
network with community structure generator. In: Proceedings of ECML PKDD.
pp. 41–44 (2016)
5. Bonifati, A., Fletcher, G., Voigt, H., Yakovets, N.: Querying graphs. Synthesis
Lectures on Data Management 10(3), 1–184 (2018)
6. Brohee, S., Van Helden, J.: Evaluation of clustering algorithms for protein-protein
interaction networks. BMC bioinformatics 7(1), 488 (2006)
7. Flake, G.W., Lawrence, S., Giles, C.L., Coetzee, F.M.: Self-organization and identification of web communities. Computer 35(3), 66–71 (2002)
8. Fortunato, S.: Community detection in graphs. Physics reports 486(3-5), 75–174(2010)
9. George, B., Kim, S., Shekhar, S.: Spatio-temporal network databases and routing
algorithms: A summary of results. In: Proceedings of SSTD. pp. 460–477 (2007)
10. Girvan, M., Newman, M.E.: Community structure in social and biological networks.
Proceedings of the national academy of sciences 99(12), 7821–7826 (2002)
11. Huang, X., Li, J., Hu, X.: Accelerated attributed network embedding. In: Proceedings of SIAM SDM. pp. 633–641 (2017)

16

S. Maekawa et al.

12. Huang, Z., Ye, Y., Li, X., Liu, F., Chen, H.: Joint weighted nonnegative matrix
factorization for mining attributed graphs. In: Proceedings of PAKDD. pp. 368–380(2017)
13. Jain, A., Zamir, A.R., Savarese, S., Saxena, A.: Structural-rnn: Deep learning on
spatio-temporal graphs. In: Proceedings of CVPR. pp. 5308–5317 (2016)
14. Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning
irregular graphs. SIAM Journal on scientific Computing 20(1), 359–392 (1998)
15. Kulis, B., Basu, S., Dhillon, I., Mooney, R.: Semi-supervised graph clustering: akernel approach. Machine learning 74(1), 1–22 (2009)
16. Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Physical review E 78(4), 046110 (2008)
17. Largeron, C., Mougel, P.N., Rabbany, R., Zaı̈ane, O.R.: Generating attributed
networks with communities. PloS one 10(4), e0122777 (2015)
18. Leskovec, J., Chakrabarti, D., Kleinberg, J., Faloutsos, C., Ghahramani, Z.: Kronecker graphs: An approach to modeling networks. Journal of machine learning
research 11(Feb), 985–1042 (2010)
19. Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection.
http://snap.stanford.edu/data (Jun 2014)
20. Maekawa, S., Takeuch, K., Onizuka, M.: Non-linear Attributed Graph Clusteringby Symmetric NMF with PU Learning. arXiv preprint arXiv:1810.00946 (2018)
21. Newman, M.E.: Modularity and community structure in networks. Proceedings ofthe national academy of sciences 103(23), 8577–8582 (2006)
22. Newman, M.E.: Networks: An Introduction. Oxford University Press (2010)
23. Parimala, M., Lopez, D.: Graph clustering based on structural attribute neighborhood similarity (sans). In: Proceedings of IEEE ICECCT. pp. 1–4 (2015)24. Park, H., Kim, M.S.: EvoGraph: an effective and efficient graph upscaling method
for preserving graph properties. In: Proceedings of KDD. pp. 2051–2059 (2018)25. Sahu, S., Mhedhbi, A., Salihoglu, S., Lin, J., Özsu, M.T.: The Ubiquity of Large
Graphs and Surprising Challenges of Graph Processing. PVLDB (2017)26. Sengupta, N., Hamann, M., Wagner, D.: Benchmark generator for dynamic overlapping communities in networks. In: Proceedings of ICDM. pp. 415–424 (2017)
27. Xu, Z., Ke, Y., Wang, Y., Cheng, H., Cheng, J.: A model-based approach to attributed graph clustering. In: Proceedings of SIGMOD. pp. 505–516 (2012)
28. Yang, Z., Perotti, J.I., Tessone, C.J.: Hierarchical benchmark graphs for testing
community detection algorithms. Physical review E 96(5), 052311 (2017)29. Yeung, K.Y., Ruzzo, W.L.: Details of the adjusted rand index and clustering algorithms, supplement to the paper an empirical study on principal component
analysis for clustering gene expression data. Bioinformatics 17(9), 763–774 (2001)
30. You, J., Ying, R., Ren, X., Hamilton, W.L., Leskovec, J.: GraphRNN: a deep
generative model for graphs. arXiv preprint arXiv:1802.08773 (2018)
31. Zhang, Z., Yang, H., Bu, J., Zhou, S., Yu, P., Zhang, J., Ester, M., Wang, C.:
ANRL: Attributed network representation learning via deep neural networks. In:
Proceedings of IJCAI. pp. 3155–3161 (2018)