[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] select node with probability proportional to degree
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] select node with probability proportional to degree |
Date: |
Mon, 21 Mar 2011 23:38:29 +0100 |
> I would like to select nodes in my network with a probability proportional to
> a node's attribute or structural properties, i.e. degree.
> Any hint on the python best way to accomplish this task is more than welcome.
1. Take the cumulative sum of the degrees (i.e. calculate a list where element
i is the sum of the elements in the original list from index 0 to index i,
inclusive).
2. Generate a random integer between 0 and the last element of the cumulative
sum list (which is also the largest btw).
3. Using binary search (see the bisect module), find the index in the
cumulative sum list where the generated random number should be inserted to
keep the list sorted. This index is the index of the node you are looking for.
--
T.