D-Wave NetworkX¶
D-Wave NetworkX is an extension of NetworkX—a Python language package for exploration and analysis of networks and network algorithms—for users of D-Wave Systems. It provides tools for working with Chimera graphs and implementations of graph-theory algorithms on the D-Wave system and other binary quadratic model samplers.
The example below generates a graph for a Chimera unit cell (eight nodes in a 4-by-2 bipartite architecture).
>>> import dwave_networkx as dnx
>>> graph = dnx.chimera_graph(1, 1, 4)
See the documentation for more examples.
Installation¶
Installation from PyPi:
pip install dwave_networkx
Installation from source:
pip install -r requirements.txt
python setup.py install
License¶
Released under the Apache License 2.0.
Contributing¶
Ocean’s contributing guide has guidelines for contributing to Ocean packages.
Documentation¶
| Release: | 0.8.13 |
|---|---|
| Date: | Mar 20, 2023 |
Note
This documentation is for the latest version of dwave-networkx. Documentation for the version currently installed by dwave-ocean-sdk is here: dwave-networkx.
Introduction¶
D-Wave NetworkX provides tools for working with Chimera and Pegasus graphs and implementations of graph-theory algorithms on the D-Wave system and other binary quadratic model samplers; for example, functions such as draw_chimera() provide easy visualization for Chimera graphs; functions such as maximum_cut() or min_vertex_cover() provide graph algorithms useful to optimization problems that fit well with the D-Wave system.
Like the D-Wave system, all other supported samplers must have sample_qubo and sample_ising methods for solving Ising and QUBO models and return an iterable of samples in order of increasing energy. You can set a default sampler using the set_default_sampler() function.
- For an introduction to quantum processing unit (QPU) topologies such as the Chimera` and Pegasus graphs, see Topology.
- For an introduction to binary quadratic models (BQMs), see Binary Quadratic Models.
- For an introduction to samplers, see Samplers and Composites.
Example¶
Below you can see how to create Chimera graphs implemented in the D-Wave 2X and D-Wave 2000Q systems:
import dwave_networkx as dnx
# D-Wave 2X
C = dnx.chimera_graph(12, 12, 4)
# D-Wave 2000Q
C = dnx.chimera_graph(16, 16, 4)
Reference Documentation¶
Release: 0.8.13 Date: Mar 20, 2023
Algorithms¶
Implementations of graph-theory algorithms on the D-Wave system and other binary quadratic model samplers.
Canonicalization¶
canonical_chimera_labeling(G[, t]) |
Returns a mapping from the labels of G to chimera-indexed labeling. |
Clique¶
A clique in an undirected graph G = (V, E) is a subset of the vertex set such that for every two vertices in C there exists an edge connecting the two.
maximum_clique(G[, sampler, lagrange]) |
Returns an approximate maximum clique. |
clique_number(G[, sampler, lagrange]) |
Returns the number of vertices in the maximum clique of a graph. |
is_clique(G, clique_nodes) |
Determines whether the given nodes form a clique. |
Coloring¶
Graph coloring is the problem of assigning a color to the vertices of a graph in a way that no adjacent vertices have the same color.
Example¶
The map-coloring problem is to assign a color to each region of a map (represented by a vertex on a graph) such that any two regions sharing a border (represented by an edge of the graph) have different colors.
Coloring a map of Canada with four colors.
is_vertex_coloring(G, coloring) |
Determines whether the given coloring is a vertex coloring of graph G. |
min_vertex_color(G[, sampler, chromatic_lb, …]) |
Returns an approximate minimum vertex coloring. |
min_vertex_color_qubo(G[, chromatic_lb, …]) |
Return a QUBO with ground states corresponding to a minimum vertex coloring. |
vertex_color(G, colors[, sampler]) |
Returns an approximate vertex coloring. |
vertex_color_qubo(G, colors) |
Return the QUBO with ground states corresponding to a vertex coloring. |
Cover¶
Vertex covering is the problem of finding a set of vertices such that all the edges of the graph are incident to at least one of the vertices in the set.
Cover for a Chimera unit cell: the nodes of both the blue set of vertices (the horizontal tile of the Chimera unit cell) and the red set (vertical tile) connect to all 16 edges of the graph.
min_weighted_vertex_cover(G[, weight, …]) |
Returns an approximate minimum weighted vertex cover. |
min_vertex_cover(G[, sampler, lagrange]) |
Returns an approximate minimum vertex cover. |
is_vertex_cover(G, vertex_cover) |
Determines whether the given set of vertices is a vertex cover of graph G. |
Elimination Ordering¶
Many algorithms for NP-hard problems are exponential in treewidth. However, finding a lower bound on treewidth is in itself NP-complete. [GD] describes a branch-and-bound algorithm for computing the treewidth of an undirected graph by searching in the space of perfect elimination ordering of vertices of the graph.
A clique of a graph is a fully-connected subset of vertices; that is, every pair of vertices in the clique share an edge. A simplicial vertex is one whose neighborhood induces a clique. A perfect elimination ordering is an ordering of vertices \(1..n\) such that any vertex \(i\) is simplicial for the subset of vertices \(i..n\).
chimera_elimination_order(m[, n, t, coordinates]) |
Provides a variable elimination order for a Chimera graph. |
elimination_order_width(G, order) |
Calculates the width of the tree decomposition induced by a variable elimination order. |
is_almost_simplicial(G, n) |
Determines whether a node n in G is almost simplicial. |
is_simplicial(G, n) |
Determines whether a node n in G is simplicial. |
max_cardinality_heuristic(G) |
Computes an upper bound on the treewidth of graph G based on the max-cardinality heuristic for the elimination ordering. |
minor_min_width(G) |
Computes a lower bound for the treewidth of graph G. |
min_fill_heuristic(G) |
Computes an upper bound on the treewidth of graph G based on the min-fill heuristic for the elimination ordering. |
min_width_heuristic(G) |
Computes an upper bound on the treewidth of graph G based on the min-width heuristic for the elimination ordering. |
pegasus_elimination_order(n[, coordinates]) |
Provides a variable elimination order for the Pegasus graph. |
treewidth_branch_and_bound(G[, …]) |
Computes the treewidth of graph G and a corresponding perfect elimination ordering. |
References¶
| [GD] | Gogate & Dechter. “A Complete Anytime Algorithm for Treewidth.” https://arxiv.org/abs/1207.4109 |
Markov Networks¶
sample_markov_network(MN[, sampler, …]) |
Samples from a markov network using the provided sampler. |
markov_network_bqm(MN) |
Construct a binary quadratic model for a markov network. |
Matching¶
A matching is a subset of graph edges in which no vertex occurs more than once.
A matching for a Chimera unit cell: no vertex is incident to more than one edge in the set of blue edges
matching_bqm(G) |
Find a binary quadratic model for the graph’s matchings. |
maximal_matching_bqm(G[, lagrange]) |
Find a binary quadratic model for the graph’s maximal matchings. |
min_maximal_matching_bqm(G[, …]) |
Find a binary quadratic model for the graph’s minimum maximal matchings. |
min_maximal_matching(G[, sampler]) |
Returns an approximate minimum maximal matching. |
Maximum Cut¶
A maximum cut is a subset of a graph’s vertices such that the number of edges between this subset and the remaining vertices is as large as possible.
Maximum cut for a Chimera unit cell: the blue line around the subset of nodes {4, 5, 6, 7} cuts 16 edges; adding or removing a node decreases the number of edges between the two complementary subsets of the graph.
maximum_cut(G[, sampler]) |
Returns an approximate maximum cut. |
weighted_maximum_cut(G[, sampler]) |
Returns an approximate weighted maximum cut. |
Independent Set¶
An independent set is a set of a graph’s vertices with no edge connecting any of its member pairs.
Independent sets for a Chimera unit cell: the nodes of both the blue set of vertices (the horizontal tile of the Chimera unit cell) and the red set (vertical tile) are independent sets of the graph, with no blue node adjacent to another blue node and likewise for red nodes.
maximum_weighted_independent_set(G[, …]) |
Returns an approximate maximum weighted independent set. |
maximum_independent_set(G[, sampler, lagrange]) |
Returns an approximate maximum independent set. |
is_independent_set(G, indep_nodes) |
Determines whether the given nodes form an independent set. |
Helper Functions¶
maximum_weighted_independent_set_qubo(G[, …]) |
Return the QUBO with ground states corresponding to a maximum weighted independent set. |
Partitioning¶
A k-partition consists of k disjoint and equally sized subsets of a graph’s vertices such that the total number of edges between nodes in distinct subsets is as small as possible.
A 2-partition for a simple graph: the nodes in blue are in the ‘0’ subset, and the nodes in red are in the ‘1’ subset. There are no other arrangements with fewer edges between two equally sized subsets.
partition(G[, num_partitions, sampler]) |
Returns an approximate k-partition of G. |
Traveling Salesperson¶
A traveling salesperson route is an ordering of the vertices in a complete weighted graph.
A traveling salesperson route of [2, 1, 0, 3].
traveling_salesperson(G[, sampler, …]) |
Returns an approximate minimum traveling salesperson route. |
traveling_salesperson_qubo(G[, lagrange, …]) |
Return the QUBO with ground states corresponding to a minimum TSP route. |
Drawing¶
Tools to visualize topologies of D-Wave QPUs and weighted graph problems on them.
Chimera Graph Functions¶
Tools to visualize Chimera lattices and weighted graph problems on them.
chimera_layout(G[, scale, center, dim]) |
Positions the nodes of graph G in a Chimera layout. |
chimera_node_placer_2d(m, n, t[, scale, …]) |
Generates a function that converts Chimera indices to x- and y-coordinates for a plot. |
draw_chimera(G, **kwargs) |
Draws graph G in a Chimera layout. |
draw_chimera_embedding(G, *args, **kwargs) |
Draws an embedding onto the Chimera graph G. |
draw_chimera_yield(G, **kwargs) |
Draws graph G with highlighted faults. |
Example¶
This example uses the chimera_layout() function to show the positions
of nodes of a simple 5-node NetworkX graph in a Chimera lattice. It then uses the
chimera_graph() and draw_chimera() functions to display those
positions on a Chimera unit cell.
>>> import networkx as nx
>>> import dwave_networkx as dnx
>>> import matplotlib.pyplot as plt
>>> H = nx.Graph()
>>> H.add_nodes_from([0, 4, 5, 6, 7])
>>> H.add_edges_from([(0, 4), (0, 5), (0, 6), (0, 7)])
>>> pos=dnx.chimera_layout(H)
>>> pos
{0: array([ 0. , -0.5]),
4: array([ 0.5, 0. ]),
5: array([ 0.5 , -0.25]),
6: array([ 0.5 , -0.75]),
7: array([ 0.5, -1. ])}
>>> # Show graph H on a Chimera unit cell
>>> plt.ion()
>>> G=dnx.chimera_graph(1, 1, 4) # Draw a Chimera unit cell
>>> dnx.draw_chimera(G)
>>> dnx.draw_chimera(H, node_color='b', node_shape='*', style='dashed', edge_color='b', width=3)
>>> # matplotlib commands to add labels to graphic not shown
Graph H (blue) overlaid on a Chimera unit cell (red nodes and black edges),
which is rendered in a cross layout.
Pegasus Graph Functions¶
Tools to visualize Pegasus lattices and weighted graph problems on them.
draw_pegasus(G[, crosses]) |
Draws graph G in a Pegasus topology. |
draw_pegasus_embedding(G, *args, **kwargs) |
Draws an embedding onto Pegasus graph G. |
draw_pegasus_yield(G, **kwargs) |
Draws graph G with highlighted faults. |
pegasus_layout(G[, scale, center, dim, crosses]) |
Positions the nodes of graph G in a Pegasus topology. |
pegasus_node_placer_2d(G[, scale, center, …]) |
Generates a function to convert Pegasus indices to plottable coordinates. |
Example¶
This example uses the draw_pegasus() function to show the positions
of nodes of a simple 5-node graph on a small Pegasus lattice.
>>> import dwave_networkx as dnx
>>> import matplotlib.pyplot as plt
>>> G = dnx.pegasus_graph(2)
>>> H = dnx.pegasus_graph(2, node_list=[4, 40, 41, 42, 43],
edge_list=[(4, 40), (4, 41), (4, 42), (4, 43)])
>>> # Show graph H on a small Pegasus lattice
>>> plt.ion()
>>> # Show graph H on a small Pegasus lattice
>>> plt.ion()
>>> dnx.draw_pegasus(G, with_labels=True, crosses=True, node_color="Yellow")
>>> dnx.draw_pegasus(H, crosses=True, node_color='b', style='dashed',
edge_color='b', width=3)
Graph H (blue) overlaid on a small Pegasus lattice (yellow nodes and black edges),
which is rendered in a cross layout.
Zephyr Graph Functions¶
Tools to visualize Zephyr lattices and weighted graph problems on them.
draw_zephyr(G, **kwargs) |
Draws graph G in a Zephyr topology. |
draw_zephyr_embedding(G, *args, **kwargs) |
Draws an embedding onto a Zephyr graph G. |
draw_zephyr_yield(G, **kwargs) |
Draws graph G with highlighted faults, according to the Zephyr layout. |
zephyr_layout(G[, scale, center, dim]) |
Positions the nodes of graph G in a Zephyr topology. |
zephyr_node_placer_2d(G[, scale, center, dim]) |
Generates a function to convert Zephyr indices to plottable coordinates. |
Example¶
This example uses the draw_zephyr_embedding() function to show the positions
of a five-node clique on a small Zephyr graph.
>>> import dwave_networkx as dnx
>>> import matplotlib.pyplot as plt
>>> import networkx as nx
...
>>> G = dnx.zephyr_graph(1)
>>> embedding = {"N1": [13, 44], "N2": [11], "N3": [41], "N4": [40], "N5": [9, 37]}
...
>>> plt.ion()
>>> dnx.draw_zephyr_embedding(G, embedding, show_labels=True)
Five-node clique embedded in a small Zephyr graph.
Graph Generators¶
Generators for graphs, such the graphs (topologies) of D-Wave System QPUs.
D-Wave Systems¶
chimera_graph(m[, n, t, create_using, …]) |
Creates a Chimera lattice of size (m, n, t). |
pegasus_graph(m[, create_using, node_list, …]) |
Creates a Pegasus graph with size parameter m. |
zephyr_graph(m[, t, create_using, …]) |
Creates a Zephyr graph with grid parameter m and tile parameter t. |
Example¶
This example uses the the chimera_graph() function to create a Chimera lattice of size (1, 1, 4), which is a single unit cell in Chimera topology, and the find_chimera() function to determine the Chimera indices.
>>> import networkx as nx
>>> import dwave_networkx as dnx
>>> G = dnx.chimera_graph(1, 1, 4)
>>> chimera_indices = dnx.find_chimera_indices(G)
>>> print chimera_indices
{0: (0, 0, 0, 0),
1: (0, 0, 0, 1),
2: (0, 0, 0, 2),
3: (0, 0, 0, 3),
4: (0, 0, 1, 0),
5: (0, 0, 1, 1),
6: (0, 0, 1, 2),
7: (0, 0, 1, 3)}
Indices of a Chimera unit cell found by creating a lattice of size (1, 1, 4).
Toruses¶
chimera_torus(m[, n, t, node_list, edge_list]) |
Creates a defect-free Chimera lattice of size \((m, n, t)\) subject to periodic boundary conditions. |
pegasus_torus(m[, node_list, edge_list, …]) |
Creates a Pegasus graph modified to allow for periodic boundary conditions and translational invariance. |
zephyr_torus(m[, t, node_list, edge_list]) |
Creates a Zephyr graph modified to allow for periodic boundary conditions and translational invariance. |
Other Graphs¶
markov_network(potentials) |
Creates a Markov Network from potentials. |
Utilities¶
Decorators¶
Decorators allow for input checking and default parameter setting for algorithms.
binary_quadratic_model_sampler(which_args) |
Decorator to validate sampler arguments. |
Coordinates Conversion¶
-
class
chimera_coordinates(m, n=None, t=None)[source]¶ Provides coordinate converters for the chimera indexing scheme.
Parameters: Examples
Convert between Chimera coordinates and linear indices directly
>>> coords = dnx.chimera_coordinates(16, 16, 4) >>> coords.chimera_to_linear((0, 2, 0, 1)) 17 >>> coords.linear_to_chimera(17) (0, 2, 0, 1)
Construct a new graph with the coordinate labels
>>> C16 = dnx.chimera_graph(16) >>> coords = dnx.chimera_coordinates(16) >>> G = nx.Graph() >>> G.add_nodes_from(coords.iter_linear_to_chimera(C16.nodes)) >>> G.add_edges_from(coords.iter_linear_to_chimera_pairs(C16.edges))
See also
chimera_graph()- Describes the various conventions.
-
class
pegasus_coordinates(m)[source]¶ Provides coordinate converters for the Pegasus indexing schemes.
Parameters: m (int) – Size parameter for the Pegasus lattice. See also
pegasus_graph()- Describes the various coordinate conventions.
-
class
zephyr_coordinates(m, t=4)[source]¶ Provides coordinate converters for the Zephyr indexing schemes.
Parameters: See also
zephyr_graph()- Describes the various coordinate conventions.
Graph Indexing¶
See Coordinates Conversion on instantiating the needed lattice size and setting correct domain and range for coordinates in a QPU working graph.
For the iterator versions of these functions, see the code.
Chimera¶
chimera_coordinates.chimera_to_linear(q) |
Convert a 4-term Chimera coordinate to a linear index. |
chimera_coordinates.linear_to_chimera(r) |
Convert a linear index to a 4-term Chimera coordinate. |
find_chimera_indices(G) |
Attempts to determine the Chimera indices of the nodes in graph G. |
Pegasus¶
pegasus_coordinates.linear_to_nice(r) |
Convert a linear index into a 5-term nice coordinate. |
pegasus_coordinates.linear_to_pegasus(r) |
Convert a linear index into a 4-term Pegasus coordinate. |
pegasus_coordinates.nice_to_linear(n) |
Convert a 5-term nice coordinate into a linear index. |
pegasus_coordinates.nice_to_pegasus(n) |
Convert a 5-term nice coordinate into a 4-term Pegasus coordinate. |
pegasus_coordinates.pegasus_to_linear(q) |
Convert a 4-term Pegasus coordinate into a linear index. |
pegasus_coordinates.pegasus_to_nice(p) |
Convert a 4-term Pegasus coordinate to a 5-term nice coordinate. |
Zephyr¶
zephyr_coordinates.graph_to_linear(g) |
Return a copy of the graph g relabeled to have linear indices |
zephyr_coordinates.graph_to_zephyr(g) |
Return a copy of the graph g relabeled to have zephyr coordinates |
zephyr_coordinates.iter_linear_to_zephyr(rlist) |
Return an iterator converting a sequence of linear indices to 5-term Zephyr coordinates. |
zephyr_coordinates.iter_linear_to_zephyr_pairs(plist) |
Return an iterator converting a sequence of pairs of linear indices to pairs of 5-term Zephyr coordinates. |
zephyr_coordinates.iter_zephyr_to_linear(qlist) |
Return an iterator converting a sequence of 5-term Zephyr coordinates to linear indices. |
zephyr_coordinates.iter_zephyr_to_linear_pairs(plist) |
Return an iterator converting a sequence of pairs of 5-term Zephyr coordinates to pairs of linear indices. |
zephyr_coordinates.linear_to_zephyr(r) |
Convert a linear index into a 5-term Zephyr coordinate. |
zephyr_coordinates.zephyr_to_linear(q) |
Convert a 5-term Zephyr coordinate into a linear index. |
zephyr_sublattice_mappings(source, target[, …]) |
Yields mappings from a Chimera or Zephyr graph into a Zephyr graph. |
Exceptions¶
Base exceptions and errors for D-Wave NetworkX.
All exceptions are derived from NetworkXException.
DWaveNetworkXException |
Base class for exceptions in DWaveNetworkX. |
DWaveNetworkXMissingSampler |
Exception raised by an algorithm requiring a discrete model sampler when none is provided. |
Default sampler¶
Sets a binary quadratic model sampler used by default for functions that require a sample when none is specified.
A sampler is a process that samples from low-energy states in models defined by an Ising equation or a Quadratic Unconstrained Binary Optimization Problem (QUBO).
Sampler API¶
- Required Methods: ‘sample_qubo’ and ‘sample_ising’
- Return value: iterable of samples, in order of increasing energy
See dimod for details.
Example
This example creates and uses a placeholder for binary quadratic model samplers that returns a correct response only in the case of finding an independent set on a complete graph (where one node is always an independent set). The placeholder sampler can be used to test the simple examples of the functions for configuring a default sampler.
>>> # Create a placeholder sampler
>>> class ExampleSampler:
... # an example sampler, only works for independent set on complete
... # graphs
... def __init__(self, name):
... self.name = name
... def sample_ising(self, h, J):
... sample = {v: -1 for v in h}
... sample[0] = 1 # set one node to true
... return [sample]
... def sample_qubo(self, Q):
... sample = {v: 0 for v in set().union(*Q)}
... sample[0] = 1 # set one node to true
... return [sample]
... def __str__(self):
... return self.name
...
>>> # Identify the new sampler as the default sampler
>>> sampler0 = ExampleSampler('sampler0')
>>> dnx.set_default_sampler(sampler0)
>>> # Find an independent set using the default sampler
>>> G = nx.complete_graph(5)
>>> dnx.maximum_independent_set(G)
[0]
Functions¶
set_default_sampler(sampler) |
Sets a default binary quadratic model sampler. |
unset_default_sampler() |
Resets the default sampler back to None. |
get_default_sampler() |
Queries the current default sampler. |
Bibliography¶
| [NX] |
|
| [GD] |
|
| [AL] |
|
| [FIA] |
|
| [DWMP] |
|
| [BBRR] |
|
| [BRK] |
|
| [RH] |
|
Installation¶
Installation from PyPi:
pip install dwave_networkx
Installation from source:
pip install -r requirements.txt
python setup.py install
License¶
Apache License
Version 2.0, January 2004
http://www.apache.org/licenses/
TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
Definitions.
“License” shall mean the terms and conditions for use, reproduction, and distribution as defined by Sections 1 through 9 of this document.
“Licensor” shall mean the copyright owner or entity authorized by the copyright owner that is granting the License.
“Legal Entity” shall mean the union of the acting entity and all other entities that control, are controlled by, or are under common control with that entity. For the purposes of this definition, “control” means (i) the power, direct or indirect, to cause the direction or management of such entity, whether by contract or otherwise, or (ii) ownership of fifty percent (50%) or more of the outstanding shares, or (iii) beneficial ownership of such entity.
“You” (or “Your”) shall mean an individual or Legal Entity exercising permissions granted by this License.
“Source” form shall mean the preferred form for making modifications, including but not limited to software source code, documentation source, and configuration files.
“Object” form shall mean any form resulting from mechanical transformation or translation of a Source form, including but not limited to compiled object code, generated documentation, and conversions to other media types.
“Work” shall mean the work of authorship, whether in Source or Object form, made available under the License, as indicated by a copyright notice that is included in or attached to the work (an example is provided in the Appendix below).
“Derivative Works” shall mean any work, whether in Source or Object form, that is based on (or derived from) the Work and for which the editorial revisions, annotations, elaborations, or other modifications represent, as a whole, an original work of authorship. For the purposes of this License, Derivative Works shall not include works that remain separable from, or merely link (or bind by name) to the interfaces of, the Work and Derivative Works thereof.
“Contribution” shall mean any work of authorship, including the original version of the Work and any modifications or additions to that Work or Derivative Works thereof, that is intentionally submitted to Licensor for inclusion in the Work by the copyright owner or by an individual or Legal Entity authorized to submit on behalf of the copyright owner. For the purposes of this definition, “submitted” means any form of electronic, verbal, or written communication sent to the Licensor or its representatives, including but not limited to communication on electronic mailing lists, source code control systems, and issue tracking systems that are managed by, or on behalf of, the Licensor for the purpose of discussing and improving the Work, but excluding communication that is conspicuously marked or otherwise designated in writing by the copyright owner as “Not a Contribution.”
“Contributor” shall mean Licensor and any individual or Legal Entity on behalf of whom a Contribution has been received by Licensor and subsequently incorporated within the Work.
Grant of Copyright License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable copyright license to reproduce, prepare Derivative Works of, publicly display, publicly perform, sublicense, and distribute the Work and such Derivative Works in Source or Object form.
Grant of Patent License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable (except as stated in this section) patent license to make, have made, use, offer to sell, sell, import, and otherwise transfer the Work, where such license applies only to those patent claims licensable by such Contributor that are necessarily infringed by their Contribution(s) alone or by combination of their Contribution(s) with the Work to which such Contribution(s) was submitted. If You institute patent litigation against any entity (including a cross-claim or counterclaim in a lawsuit) alleging that the Work or a Contribution incorporated within the Work constitutes direct or contributory patent infringement, then any patent licenses granted to You under this License for that Work shall terminate as of the date such litigation is filed.
Redistribution. You may reproduce and distribute copies of the Work or Derivative Works thereof in any medium, with or without modifications, and in Source or Object form, provided that You meet the following conditions:
- You must give any other recipients of the Work or Derivative Works a copy of this License; and
- You must cause any modified files to carry prominent notices stating that You changed the files; and
- You must retain, in the Source form of any Derivative Works that You distribute, all copyright, patent, trademark, and attribution notices from the Source form of the Work, excluding those notices that do not pertain to any part of the Derivative Works; and
- If the Work includes a “NOTICE” text file as part of its distribution, then any Derivative Works that You distribute must include a readable copy of the attribution notices contained within such NOTICE file, excluding those notices that do not pertain to any part of the Derivative Works, in at least one of the following places: within a NOTICE text file distributed as part of the Derivative Works; within the Source form or documentation, if provided along with the Derivative Works; or, within a display generated by the Derivative Works, if and wherever such third-party notices normally appear. The contents of the NOTICE file are for informational purposes only and do not modify the License. You may add Your own attribution notices within Derivative Works that You distribute, alongside or as an addendum to the NOTICE text from the Work, provided that such additional attribution notices cannot be construed as modifying the License.
You may add Your own copyright statement to Your modifications and may provide additional or different license terms and conditions for use, reproduction, or distribution of Your modifications, or for any such Derivative Works as a whole, provided Your use, reproduction, and distribution of the Work otherwise complies with the conditions stated in this License.
Submission of Contributions. Unless You explicitly state otherwise, any Contribution intentionally submitted for inclusion in the Work by You to the Licensor shall be under the terms and conditions of this License, without any additional terms or conditions. Notwithstanding the above, nothing herein shall supersede or modify the terms of any separate license agreement you may have executed with Licensor regarding such Contributions.
Trademarks. This License does not grant permission to use the trade names, trademarks, service marks, or product names of the Licensor, except as required for reasonable and customary use in describing the origin of the Work and reproducing the content of the NOTICE file.
Disclaimer of Warranty. Unless required by applicable law or agreed to in writing, Licensor provides the Work (and each Contributor provides its Contributions) on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied, including, without limitation, any warranties or conditions of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A PARTICULAR PURPOSE. You are solely responsible for determining the appropriateness of using or redistributing the Work and assume any risks associated with Your exercise of permissions under this License.
Limitation of Liability. In no event and under no legal theory, whether in tort (including negligence), contract, or otherwise, unless required by applicable law (such as deliberate and grossly negligent acts) or agreed to in writing, shall any Contributor be liable to You for damages, including any direct, indirect, special, incidental, or consequential damages of any character arising as a result of this License or out of the use or inability to use the Work (including but not limited to damages for loss of goodwill, work stoppage, computer failure or malfunction, or any and all other commercial damages or losses), even if such Contributor has been advised of the possibility of such damages.
Accepting Warranty or Additional Liability. While redistributing the Work or Derivative Works thereof, You may choose to offer, and charge a fee for, acceptance of support, warranty, indemnity, or other liability obligations and/or rights consistent with this License. However, in accepting such obligations, You may act only on Your own behalf and on Your sole responsibility, not on behalf of any other Contributor, and only if You agree to indemnify, defend, and hold each Contributor harmless for any liability incurred by, or claims asserted against, such Contributor by reason of your accepting any such warranty or additional liability.
Social¶
A signed social network graph is a graph whose signed edges represent friendly/hostile interactions between vertices.
A signed social graph for three nodes, where Eve and Bob are friendly with each other and hostile to Alice. This network is balanced because it can be cleanly divided into two subsets, {Bob, Eve} and {Alice}, with friendly relations within each subset and only hostile relations between the subsets.
structural_imbalance(S[, sampler])structural_imbalance_ising(S)