Skip to main content
`Ctrl`+`K`

# Source code for networkx.generators.intersection

    """
    Generators for random intersection graphs.
    """

    import networkx as nx
    from networkx.utils import py_random_state

    __all__ = [
        "uniform_random_intersection_graph",
        "k_random_intersection_graph",
        "general_random_intersection_graph",
    ]

    @py_random_state(3)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def uniform_random_intersection_graph(n, m, p, seed=None):
        """Returns a uniform random intersection graph.

        Parameters
        ----------
        n : int
            The number of nodes in the first bipartite set (nodes)
        m : int
            The number of nodes in the second bipartite set (attributes)
        p : float
            Probability of connecting nodes between bipartite sets
        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

        See Also
        --------
        gnp_random_graph

        References
        ----------
        .. [1] K.B. Singer-Cohen, Random Intersection Graphs, 1995,
           PhD thesis, Johns Hopkins University
        .. [2] Fill, J. A., Scheinerman, E. R., and Singer-Cohen, K. B.,
           Random intersection graphs when m = !(n):
           An equivalence theorem relating the evolution of the g(n, m, p)
           and g(n, p) models. Random Struct. Algorithms 16, 2 (2000), 156–176.
        """
        from networkx.algorithms import bipartite

        G = bipartite.random_graph(n, m, p, seed)
        return nx.projected_graph(G, range(n))

    @py_random_state(3)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def k_random_intersection_graph(n, m, k, seed=None):
        """Returns a intersection graph with randomly chosen attribute sets for
        each node that are of equal size (k).

        Parameters
        ----------
        n : int
            The number of nodes in the first bipartite set (nodes)
        m : int
            The number of nodes in the second bipartite set (attributes)
        k : float
            Size of attribute set to assign to each node.
        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

        See Also
        --------
        gnp_random_graph, uniform_random_intersection_graph

        References
        ----------
        .. [1] Godehardt, E., and Jaworski, J.
           Two models of random intersection graphs and their applications.
           Electronic Notes in Discrete Mathematics 10 (2001), 129--132.
        """
        G = nx.empty_graph(n + m)
        mset = range(n, n + m)
        for v in range(n):
            targets = seed.sample(mset, k)
            G.add_edges_from(zip([v] * len(targets), targets))
        return nx.projected_graph(G, range(n))

    @py_random_state(3)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def general_random_intersection_graph(n, m, p, seed=None):
        """Returns a random intersection graph with independent probabilities
        for connections between node and attribute sets.

        Parameters
        ----------
        n : int
            The number of nodes in the first bipartite set (nodes)
        m : int
            The number of nodes in the second bipartite set (attributes)
        p : list of floats of length m
            Probabilities for connecting nodes to each attribute
        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

        See Also
        --------
        gnp_random_graph, uniform_random_intersection_graph

        References
        ----------
        .. [1] Nikoletseas, S. E., Raptopoulos, C., and Spirakis, P. G.
           The existence and efficient construction of large independent sets
           in general random intersection graphs. In ICALP (2004), J. D´ıaz,
           J. Karhum¨aki, A. Lepist¨o, and D. Sannella, Eds., vol. 3142
           of Lecture Notes in Computer Science, Springer, pp. 1029–1040.
        """
        if len(p) != m:
            raise ValueError("Probability list p must have m elements.")
        G = nx.empty_graph(n + m)
        mset = range(n, n + m)
        for u in range(n):
            for v, q in zip(mset, p):
                if seed.random() < q:
                    G.add_edge(u, v)
        return nx.projected_graph(G, range(n))