Package networkx :: Module threshold

[frames | no frames]

## Module networkx.threshold

Threshold Graphs - Creation, manipulation and identification.

Function Summary
| ``betweenness_sequence`(creation_sequence)` Return betweenness for the threshold graph with the given creation sequence.
| ``cluster_sequence`(creation_sequence)` Return cluster sequence for the given threshold graph creation sequence.
| ``creation_sequence`(degree_sequence, with_labels, compact)` Determines the creation sequence for the given threshold degree sequence.
| ``creation_sequence_to_weights`(creation_sequence)` Returns a list of node weights which create the threshold graph designated by the creation sequence.
| ``degree_correlation`(creation_sequence)` Return the degree-degree correlation over all edges.
| ``degree_sequence`(creation_sequence)` Return degree sequence for the threshold graph with the given creation sequence
| ``density`(creation_sequence)` Return the density of the graph with this creation_sequence.
| ``eigenvalues`(creation_sequence)` Return sequence of eigenvalues of the Laplacian of the threshold graph for the given creation_sequence.
| ``find_alternating_4_cycle`(G)` Returns False if there aren't any alternating 4 cycles.
| ``find_creation_sequence`(G)` Find a threshold subgraph that is close to largest in G.
| ``find_threshold_graph`(G)` Return a threshold subgraph that is close to largest in G.
| ``is_threshold_graph`(G)` Returns True if G is a threshold graph.
| ``is_threshold_sequence`(degree_sequence)` Returns True if the sequence is a threshold degree seqeunce.
| ``left_d_threshold_sequence`(n, m)` Create a skewed threshold graph with a given number of vertices (n) and a given number of edges (m).
| ``make_compact`(creation_sequence)` Returns the creation sequence in a compact form that is the number of 'i's and 'd's alternating.
| ``random_threshold_sequence`(n, p, seed)` Create a random threshold sequence of size n.
| ``right_d_threshold_sequence`(n, m)` Create a skewed threshold graph with a given number of vertices (n) and a given number of edges (m).
| ``shortest_path`(creation_sequence, u, v)` Find the shortest path between u and v in a threshold graph G with the given creation_sequence.
| ``shortest_path_length`(creation_sequence, i)` Return the shortest path length from indicated node to every other node for the threshold graph with the given creation sequence.
| ``swap_d`(cs, p_split, p_combine, seed)` Perform a "swap" operation on a threshold sequence.
| ``threshold_graph`(creation_sequence)` Create a threshold graph from the creation sequence or compact creation_sequence.
| ``triangle_sequence`(creation_sequence)` Return triangle sequence for the given threshold graph creation sequence.
| ``triangles`(creation_sequence)` Compute number of triangles in the threshold graph with the given creation sequence.
| ``uncompact`(compact_creation_sequence)` Converts a compact creation sequence for a threshold graph to a standard creation sequence (unlabeled).
| ``weights_to_creation_sequence`(weights, threshold, with_labels, compact)` Returns a creation sequence for a threshold graph determined by the weights and threshold given as input.

Variable Summary
`str` | `__author__` = `'Aric Hagberg (hagberg@lanl.gov)\nPieter Sw...`
`str` | `__credits__` = `''`
`str` | `__date__` = `'$Date: 2005-06-17 08:06:22 -0600 (Fri, 17 Ju...`
`str` | `__version__` = `'$Revision: 1049 $'`

Function Details

### betweenness_sequence(creation_sequence)

Return betweenness for the threshold graph with the given creation sequence. The result is unscaled. To scale the values to the iterval [0,1] divide by (n-1)*(n-2).

### cluster_sequence(creation_sequence)

Return cluster sequence for the given threshold graph creation sequence.

### creation_sequence(degree_sequence, with_labels=False, compact=False)

Determines the creation sequence for the given threshold degree sequence.

The creation sequence is a list of single characters 'd' or 'i': 'd' for dominating or 'i' for isolated vertices. Dominating vertices are connected to all vertices present when it is added. The first node added is by convention 'd'.

If with_labels==True: Returns a list of 2-tuples containing the vertex number and a character 'd' or 'i' which describes the type of vertex.

If compact==True: Returns the creation sequence in a compact form that is the number of 'i's and 'd's alternating. Examples: [1,2,2,3] represents d,i,i,d,d,i,i,i [3,1,2] represents d,d,d,i,d,d

Notice that the first number is the first vertex to be used for construction and so is always 'd'.

with_labels and compact cannot both be True.

Returns None if the sequence is not a threshold sequence

### creation_sequence_to_weights(creation_sequence)

Returns a list of node weights which create the threshold graph designated by the creation sequence. The weights are scaled so that the threshold is 1.0. The order of the nodes is the same as that in the creation sequence.

### degree_correlation(creation_sequence)

Return the degree-degree correlation over all edges.

### degree_sequence(creation_sequence)

Return degree sequence for the threshold graph with the given creation sequence

### density(creation_sequence)

Return the density of the graph with this creation_sequence. The density is the fraction of possible edges present.

### eigenvalues(creation_sequence)

Return sequence of eigenvalues of the Laplacian of the threshold graph for the given creation_sequence.

Based on the Ferrer's diagram method. The spectrum is integral and is the conjugate of the degree sequence.

See:

    @Article{degree-merris-1994,
     author =          {Russel Merris},
     title =   {Degree maximal graphs are Laplacian integral},
     journal =         {Linear Algebra Appl.},
     year =    {1994},
     volume =          {199},
     pages =   {381--389},
    }

### find_alternating_4_cycle(G)

Returns False if there aren't any alternating 4 cycles. Otherwise returns the cycle as [a,b,c,d] where (a,b) and (c,d) are edges and (a,c) and (b,d) are not.

### find_creation_sequence(G)

Find a threshold subgraph that is close to largest in G. Returns the labeled creation sequence of that threshold graph.

### find_threshold_graph(G)

Return a threshold subgraph that is close to largest in G. The threshold graph will contain the largest degree node in G.

If you just want the creation sequence you can use creation_sequence(find_threshold_graph(G).degree(with_labels=True), labeled=True)

### is_threshold_graph(G)

Returns True if G is a threshold graph.

### is_threshold_sequence(degree_sequence)

Returns True if the sequence is a threshold degree seqeunce.

Uses the property that a threshold graph must be constructed by adding either dominating or isolated nodes. Thus, it can be deconstructed iteratively by removing a node of degree zero or a node that connects to the remaining nodes. If this deconstruction failes then the sequence is not a threshold sequence.

### left_d_threshold_sequence(n, m)

Create a skewed threshold graph with a given number of vertices (n) and a given number of edges (m).

The routine returns an unlabeled creation sequence for the threshold graph.

FIXME: describe algorithm

### make_compact(creation_sequence)

Returns the creation sequence in a compact form that is the number of 'i's and 'd's alternating. Examples: [1,2,2,3] represents d,i,i,d,d,i,i,i. [3,1,2] represents d,d,d,i,d,d. Notice that the first number is the first vertex to be used for construction and so is always 'd'.

### random_threshold_sequence(n, p, seed=None)

Create a random threshold sequence of size n. A creation sequence is built by randomly choosing d's with probabiliy p and i's with probability 1-p.

    >>> s=random_threshold_sequence(10,0.5)

returns a threshold sequence of length 10 with equal probably of an i or a d at each position.

A "random" threshold graph can be built with

    >>> G=threshold_graph(random_threshold_sequence(n,p))

### right_d_threshold_sequence(n, m)

Create a skewed threshold graph with a given number of vertices (n) and a given number of edges (m).

The routine returns an unlabeled creation sequence for the threshold graph.

FIXME: describe algorithm

### shortest_path(creation_sequence, u, v)

Find the shortest path between u and v in a threshold graph G with the given creation_sequence.

For an unlabeled creation_sequence, the vertices u and v must be integers in (0,len(sequence)) refering to the position of the desired vertices in the sequence.

For a labeled creation_sequence, u and v are labels of veritices.

Use cs=creation_sequence(degree_sequence,with_labels=True) to convert a degree sequence to a creation sequence.

Returns a list of vertices from u to v. Example: if they are neighbors, it returns [u,v]

### shortest_path_length(creation_sequence, i)

Return the shortest path length from indicated node to every other node for the threshold graph with the given creation sequence. Node is indicated by index i in creation_sequence unless creation_sequence is labeled in which case, i is taken to be the label of the node.

Paths lengths in threshold graphs are at most 2. Length to unreachable nodes is set to -1.

### swap_d(cs, p_split=1.0, p_combine=1.0, seed=None)

Perform a "swap" operation on a threshold sequence.

The swap preserves the number of nodes and edges in the graph for the given sequence. The resulting sequence is still a threshold sequence.

Perform one split and one combine operation on the 'd's of a creation sequence for a threshold graph. This operation maintains the number of nodes and edges in the graph, but shifts the edges from node to node maintaining the threshold quality of the graph.

### threshold_graph(creation_sequence)

Create a threshold graph from the creation sequence or compact creation_sequence.

The input sequence can be a

creation sequence (e.g. ['d','i','d','d','d','i']) labeled creation sequence (e.g. [(0,'d'),(2,'d'),(1,'i')]) compact creation sequence (e.g. [2,1,1,2,0])

Use cs=creation_sequence(degree_sequence,labeled=True) to convert a degree sequence to a creation sequence.

Returns None if the sequence is not valid

### triangle_sequence(creation_sequence)

Return triangle sequence for the given threshold graph creation sequence.

### triangles(creation_sequence)

Compute number of triangles in the threshold graph with the given creation sequence.

### uncompact(compact_creation_sequence)

Converts a compact creation sequence for a threshold graph to a standard creation sequence (unlabeled). See creation_sequence.

### weights_to_creation_sequence(weights, threshold=1, with_labels=False, compact=False)

Returns a creation sequence for a threshold graph determined by the weights and threshold given as input. If the sum of two node weights is greater than the threshold value, an edge is created between these nodes.

The creation sequence is a list of single characters 'd' or 'i': 'd' for dominating or 'i' for isolated vertices. Dominating vertices are connected to all vertices present when it is added. The first node added is by convention 'd'.

If with_labels==True: Returns a list of 2-tuples containing the vertex number and a character 'd' or 'i' which describes the type of vertex.

If compact==True: Returns the creation sequence in a compact form that is the number of 'i's and 'd's alternating. Examples: [1,2,2,3] represents d,i,i,d,d,i,i,i [3,1,2] represents d,d,d,i,d,d

Notice that the first number is the first vertex to be used for construction and so is always 'd'.

with_labels and compact cannot both be True.

Variable Details

### __author__

  Type:
    `str`
  Value:

        '''Aric Hagberg (hagberg@lanl.gov)
        Pieter Swart (swart@lanl.gov)
        Dan Schult (dschult@colgate.edu)'''

### __credits__

  Type:
    `str`
  Value:

        ''

### __date__

  Type:
    `str`
  Value:

        '$Date: 2005-06-17 08:06:22 -0600 (Fri, 17 Jun 2005) $'

### __version__

  Type:
    `str`
  Value:

        '$Revision: 1049 $'

Generated by Epydoc 2.1 on Sun Aug 21 08:06:58 2005 | http://epydoc.sf.net