[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Segregating a graph

From: Tamás Nepusz
Subject: Re: [igraph] Segregating a graph
Date: Thu, 3 Apr 2014 15:35:45 +0200


There’s no pre-existing way to do this in igraph if the structure of your graph is specified in advance (in step 1). preference.game() is probably the closest to what you want to achieve, but it lets you specify the probability of occurrence for each vertex type and the probability for links between each possible vertex type pair only. The edges will then be generated independently of each other so you cannot enforce a prescribed “structure” on the graph.

An alternative option that you could try is to perform a random walk in the space of all possible type configurations while trying to optimize a goal function that describes how “close” you are to the desired segregation level. But this is probably going to be slower than your suggestion.

All the best, 

From: Thomas address@hidden
Reply: Help for igraph users address@hidden
Date: 1 April 2014 at 21:48:19
To: Help for igraph users address@hidden
Subject:  [igraph] Segregating a graph

I am about to write a routine to achieve the following, and wanted to
double check there's no pre-existing way to do this built into igraph.

1. Create a graph - say g <- watts.strogatz.game(1, 225, 5, 0.05)

2. Assign a type to each node such that a node with degree x will have
roughly a set percentage, say x*60%, of neighbours of a certain type.
Initially I'm going to use two types (1,0).

For info a rough outline of how I'm planning to implement this is below.

Thank you

Thomas Chesney


g <- watts.strogatz.game(1, 225, 5, 0.05)

Create a vector of 225 types, type <- rbinom(225, 1, 0.5)

For each node z, set x1=degree(g,a)*60% to be the number nodes of type
1 and x2=degree(g,a)*40% to be the number of nodes of type 2.

For 1 to x1, for each Type 1 in the type vector, check the node with
the same index's degree hasn't been exceeded yet and if not, join it
to node z.

For 1 to x2, for each Type 2 in the type vector, check the node with
the same index's degree hasn't been exceeded yet and if not, join it
to node z.

If a node of a certain type cannot be found for node z, join it to a
node of the other type.
This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment
may still contain software viruses which could damage your computer system, you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

igraph-help mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]