Generates a graph based with a given degree sequence and maximizing the smetric. Experimental implementation. Maximum smetrix means that high degree nodes are connected to high degree nodes.  `deg_sequence`: degree sequence, a list of integers with each entry corresponding to the degree of a node. A nongraphical degree sequence raises an Exception. Reference:: @unpublished{li2005, author = {Lun Li and David Alderson and Reiko Tanaka and John C. Doyle and Walter Willinger}, title = {Towards a Theory of ScaleFree Graphs: Definition, Properties, and Implications (Extended Version)}, url = {http://arxiv.org/abs/condmat/0501169}, year = {2005} } The algorithm STEP 0  Initialization A = {0} B = {1, 2, 3, ..., n} O = {(i; j), ..., (k, l),...} where i < j, i <= k < l and d_i * d_j >= d_k *d_l wA = d_1 dB = sum(degrees) STEP 1  Link selection (a) If O = 0 TERMINATE. Return graph A. (b) Select element(s) (i, j) in O having the largest d_i * d_j , if for any i or j either w_i = 0 or w_j = 0 delete (i, j) from O (c) If there are no elements selected go to (a). (d) Select the link (i, j) having the largest value w_i (where for each (i, j) w_i is the smaller of w_i and w_j ), and proceed to STEP 2. STEP 2  Link addition Type 1: i in A and j in B. Add j to the graph A and remove it from the set B add a link (i, j) to the graph A. Update variables: wA = wA + d_j 2 and dB = dB  d_j Decrement w_i and w_j with one. Delete (i, j) from O Type 2: i and j in A. Check Tree Condition: If dB = 2 * B  wA. Delete (i, j) from O, continue to STEP 3 Check Disconnected Cluster Condition: If wA = 2. Delete (i, j) from O, continue to STEP 3 Add the link (i, j) to the graph A Decrement w_i and w_j with one, and wA = wA 2 STEP 3 Go to STEP 1 The article states that the algorithm will result in a maximal smetric. This implementation can not guarantee such maximality. I may have misunderstood the algorithm, but I can not see how it can be anything but a heuristic. Please contact me at sundsdal@gmail.com if you can provide python code that can guarantee maximality. Several optimizations are included in this code and it may be hard to read. Commented code to come. Definition at line 477 of file degree_seq.py. 00477 : """Generates a graph based with a given degree sequence and maximizing the smetric. Experimental implementation. Maximum smetrix means that high degree nodes are connected to high degree nodes.  `deg_sequence`: degree sequence, a list of integers with each entry corresponding to the degree of a node. A nongraphical degree sequence raises an Exception. Reference:: @unpublished{li2005, author = {Lun Li and David Alderson and Reiko Tanaka and John C. Doyle and Walter Willinger}, title = {Towards a Theory of ScaleFree Graphs: Definition, Properties, and Implications (Extended Version)}, url = {http://arxiv.org/abs/condmat/0501169}, year = {2005} } The algorithm STEP 0  Initialization A = {0} B = {1, 2, 3, ..., n} O = {(i; j), ..., (k, l),...} where i < j, i <= k < l and d_i * d_j >= d_k *d_l wA = d_1 dB = sum(degrees) STEP 1  Link selection (a) If O = 0 TERMINATE. Return graph A. (b) Select element(s) (i, j) in O having the largest d_i * d_j , if for any i or j either w_i = 0 or w_j = 0 delete (i, j) from O (c) If there are no elements selected go to (a). (d) Select the link (i, j) having the largest value w_i (where for each (i, j) w_i is the smaller of w_i and w_j ), and proceed to STEP 2. STEP 2  Link addition Type 1: i in A and j in B. Add j to the graph A and remove it from the set B add a link (i, j) to the graph A. Update variables: wA = wA + d_j 2 and dB = dB  d_j Decrement w_i and w_j with one. Delete (i, j) from O Type 2: i and j in A. Check Tree Condition: If dB = 2 * B  wA. Delete (i, j) from O, continue to STEP 3 Check Disconnected Cluster Condition: If wA = 2. Delete (i, j) from O, continue to STEP 3 Add the link (i, j) to the graph A Decrement w_i and w_j with one, and wA = wA 2 STEP 3 Go to STEP 1 The article states that the algorithm will result in a maximal smetric. This implementation can not guarantee such maximality. I may have misunderstood the algorithm, but I can not see how it can be anything but a heuristic. Please contact me at sundsdal@gmail.com if you can provide python code that can guarantee maximality. Several optimizations are included in this code and it may be hard to read. Commented code to come. """ if not is_valid_degree_sequence(degree_seq): raise networkx.NetworkXError, 'Invalid degree sequence' degree_seq.sort() # make sure it's sorted degree_seq.reverse() degrees_left = degree_seq[:] A_graph = networkx.Graph() A_graph.add_node(0) a_list = [False]*len(degree_seq) b_set = set(range(1,len(degree_seq))) a_open = set([0]) O = [] for j in b_set: heapq.heappush(O, (degree_seq[0]*degree_seq[j], (0,j))) wa = degrees_left[0] #stubs in a_graph db = sum(degree_seq)  degree_seq[0] #stubs in bgraph a_list[0] = True #node 0 is now in a_Graph bsize = len(degree_seq) 1 #size of b_graph selected = [] weight = 0 while O or selected: if len(selected) <1 : firstrun = True while O: (newweight, (i,j)) = heapq.heappop(O) if degrees_left[i] < 1 or degrees_left[j] < 1 : continue if firstrun: firstrun = False weight = newweight if not newweight == weight: break heapq.heappush(selected, [degrees_left[i], \ degrees_left[j], (i,j)]) if not weight == newweight: heapq.heappush(O,(newweight, (i,j))) weight *= 1 if len(selected) < 1: break [w1, w2, (i,j)] = heapq.heappop(selected) if degrees_left[i] < 1 or degrees_left[j] < 1 : continue if a_list[i] and j in b_set: #TYPE1 a_list[j] = True b_set.remove(j) A_graph.add_node(j) A_graph.add_edge(i, j) degrees_left[i] = 1 degrees_left[j] = 1 wa += degree_seq[j]  2 db = degree_seq[j] bsize = 1 newweight = weight if not degrees_left[j] == 0: a_open.add(j) for k in b_set: if A_graph.has_edge(j, k): continue w = degree_seq[j]*degree_seq[k] if w > newweight: newweight = w if weight == w and not newweight > weight: heapq.heappush(selected, [degrees_left[j], \ degrees_left[k], (j,k)]) else: heapq.heappush(O, (w, (j,k))) if not weight == newweight: while selected: [w1,w2,(i,j)] = heapq.heappop(selected) if degrees_left[i]*degrees_left[j] > 0: heapq.heappush(O, [degree_seq[i]*degree_seq[j],(i,j)]) if degrees_left[i] == 0: a_open.discard(i) else: #TYPE2 if db == (2*bsize  wa): #tree condition #print "removing because tree condition " continue elif db < 2*bsize wa: raise networkx.NetworkXError, "THIS SHOULD NOT HAPPEN!  not graphable" continue elif wa == 2 and bsize > 0: #print "removing because disconnected cluster" #disconnected cluster condition continue elif wa == db  (bsize)*(bsize1): #print "MYOWN removing because disconnected cluster" continue A_graph.add_edge(i, j) degrees_left[i] = 1 degrees_left[j] = 1 if degrees_left[i] < 1: a_open.discard(i) if degrees_left[j] < 1: a_open.discard(j) wa = 2 if not degrees_left[i] < 0 and not degrees_left[j] < 0: selected2 = (selected) selected = [] while selected2: [w1,w1, (i,j)] = heapq.heappop(selected2) if degrees_left[i]*degrees_left[j] > 0: heapq.heappush(selected, [degrees_left[i], \ degrees_left[j], (i,j)]) return A_graph def connected_smax_graph(degree_seq):
