Ask Your Question
0

Stochastic block model

asked 2017-09-21 13:19:26 -0600

Dianbin Bao gravatar image

Hi all,

I would like to draw a random graph by Sage. The general stochastic model is the following: The graph contains $n$ vertices and the n vertices are divided into $r$ communities $C_1\cdots,C_r$. For two vertices within the same community, there is a probability $P_r$ that they are connected directly by an edge. How do I plot such a graph in Sage? References appreciated.

edit retag flag offensive close merge delete

Comments

Maybe use

sage: SetPartitions(5).random_element()
{{1, 5}, {2, 4}, {3}}
FrédéricC gravatar imageFrédéricC ( 2017-09-22 03:50:00 -0600 )edit

Are the sizes of the communities given as part of the input? Maybe this is what the comment above is trying to address.

Is the probability of edges between vertices in different communities equal to 0?

fidbc gravatar imagefidbc ( 2017-09-22 05:06:05 -0600 )edit

1 answer

Sort by » oldest newest most voted
1

answered 2017-09-22 05:29:43 -0600

fidbc gravatar image

updated 2017-09-22 07:21:42 -0600

Assuming the input consists of n, r, and the probabilities for edges within a community; and assuming that the probability of edges between vertices in different communities is 0, then here is a possible way to generate such a graph.

community_sizes = Partitions(n,length=r).random_element()
H = Graph()
for comm_size,Pr in zip(community_sizes,probs):
    H=H.disjoint_union(graphs.RandomGNP(comm_size,Pr),labels='integers')

This is assuming that n, r and probs (assumed to be a list of length r containing $P_1,P_2,\ldots,P_r$) are given as part of the input. To see the resulting graph you can use H.show().

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-09-21 13:19:26 -0600

Seen: 132 times

Last updated: Sep 22