Logo Search packages:      
Sourcecode: python-networkx version File versions  Download package

def networkx::generators::degree_seq::li_smax_graph (   degree_seq  ) 

Generates a graph based with a given degree sequence and maximizing
the s-metric.  Experimental implementation.

Maximum s-metrix  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 non-graphical degree sequence raises an Exception.    

Reference::      

  @unpublished{li-2005,
   author = {Lun Li and David Alderson and Reiko Tanaka
            and John C. Doyle and Walter Willinger},
   title = {Towards a Theory of Scale-Free Graphs:
           Definition, Properties, and  Implications (Extended Version)},
   url = {http://arxiv.org/abs/cond-mat/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 s-metric. 
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 s-metric.  Experimental implementation.

    Maximum s-metrix  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 non-graphical degree sequence raises an Exception.    

    Reference::      
    
      @unpublished{li-2005,
       author = {Lun Li and David Alderson and Reiko Tanaka
                and John C. Doyle and Walter Willinger},
       title = {Towards a Theory of Scale-Free Graphs:
               Definition, Properties, and  Implications (Extended Version)},
       url = {http://arxiv.org/abs/cond-mat/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 s-metric. 
    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 b-graph
    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)*(bsize-1):
                #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):


Generated by  Doxygen 1.6.0   Back to index