Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add function for Kuramoto model synchronization #159

Merged
merged 7 commits into from
Sep 8, 2022

Conversation

saad1282
Copy link
Contributor

Added a dynamics module and created a Kuramoto model synchronization function.

Copy link
Collaborator

@leotrs leotrs left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you for your contribution @saad1282 ! I left a few minor comments that hopefully won't be too time-consuming to address.

The algorithm it self looks good to me. It's clean and easy to read. However I'm a bit concerned about performance. I assume the operations inside the main loop are hard to vectorize since they iterate over the links/triangles, is that correct? Or are you aware of some way of writing down these operations using matrices? If we can get rid of those inner loops and write the entire computation in a single/few matrix computations then we'd gain a lot in performance.

tests/dynamics/test_synchronization.py Show resolved Hide resolved
H1 = xgi.random_hypergraph(100, [0.05, 0.001], seed=0)
r = xgi.compute_kuramoto_order_parameter(H1, 1, 1, np.ones(100), 10, 0.002)

assert len(r) == 10
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Question: this only tests the length of the output, which should always match the fifth argument in the call in the previous line, no? If so, I suggest hard-coding the actual numeric output and testing against that. There should be no problem since we are fixing the seed two lines above anyway.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We totally agree that there should be more rigorous tests. We will have to figure out better tests and your suggestion is a good option.

xgi/dynamics/synchronization.py Show resolved Hide resolved
xgi/dynamics/synchronization.py Outdated Show resolved Hide resolved
xgi/dynamics/synchronization.py Show resolved Hide resolved
xgi/dynamics/synchronization.py Outdated Show resolved Hide resolved
@nwlandry
Copy link
Collaborator

nwlandry commented Sep 6, 2022

Thank you for your contribution @saad1282 ! I left a few minor comments that hopefully won't be too time-consuming to address.

The algorithm it self looks good to me. It's clean and easy to read. However I'm a bit concerned about performance. I assume the operations inside the main loop are hard to vectorize since they iterate over the links/triangles, is that correct? Or are you aware of some way of writing down these operations using matrices? If we can get rid of those inner loops and write the entire computation in a single/few matrix computations then we'd gain a lot in performance.

Hi @leotrs. @saad1282 and I worked on implementing a numpy version (added below) and I haven't tested line-by-line but I suspect that forming the adjacency matrix and tensor is relatively expensive. Suggestions welcome!

def compute_kuramoto_order_parameter_fast(H, k2, k3, w, timesteps=10000, dt=0.002):
    """This function calculates the order parameter for the Kuramoto model on hypergraphs.

    This solves the Kuramoto model ODE on hypergraphs with edges of sizes 2 and 3
    using the Euler Method. It returns an order parameter which is a measure of synchrony.

    Parameters
    ----------
    H : Hypergraph object
        The hypergraph on which you run the Kuramoto model
    k2 : float
        The coupling strength for links
    k3 : float
        The coupling strength for triangles
    w : numpy array of real values
        The natural frequency of the nodes.
    timesteps : int greater than 1, default: 10000
        The number of timesteps for Euler Method.
    dt : float greater than 0, default: 0.002
        The size of timesteps for Euler Method.

    Returns
    -------
    r_time : numpy array of floats
        timeseries for Kuramoto model order parameter

    References
    ----------
    "Synchronization of phase oscillators on complex hypergraphs"
    by Sabina Adhikari, Juan G. Restrepo and Per Sebastian Skardal
    https://doi.org/10.48550/arXiv.2208.00909

    Examples
    --------
    >>> import numpy as np
    >>> import xgi
    >>> n = 100
    >>> H = xgi.random_hypergraph(n, [0.05, 0.001], seed=None)
    >>> w = 2*np.ones(n)
    >>> theta = np.linspace(0, 2*np.pi, n)
    >>> H.add_nodes_from(range(n))
    >>> k2 = 2
    >>> k3 = 3
    >>> R = compute_kuramoto_order_parameter(H, k2, k3, w)
    """
    H_int = xgi.convert_labels_to_integers(H, "label")
    n = H_int.num_nodes
    links = H_int.edges.filterby("size", 2).members()
    A = np.zeros([n, n])
    for i, j in links:
        A[i, j] += 1
        A[j, i] += 1

    triangles = H_int.edges.filterby("size", 3).members()

    B = np.zeros([n, n, n])

    for t in triangles:
        for i, j, k in product(t, repeat=3):
            B[i, j, k] += 1
    

    theta = np.linspace(0, 2 * np.pi, n)
    r_time = np.zeros(timesteps)

    for t in range(timesteps):

        r2 = np.zeros(n, dtype=complex)

        r1 = A.dot(np.exp(1j*theta))

        r2 = np.exp(-1j*theta).dot(B).dot(np.exp(2j*theta))

        d_theta = (
            w
            + k2 * np.multiply(r1, np.exp(-1j * theta)).imag
            + k3 * np.multiply(r2, np.exp(-1j * theta)).imag
        )
        theta_new = theta + d_theta * dt
        theta = theta_new
        z = np.mean(np.exp(1j * theta))
        r_time[t] = abs(z)

    return r_time

@leotrs
Copy link
Collaborator

leotrs commented Sep 7, 2022

    links = H_int.edges.filterby("size", 2).members()
    A = np.zeros([n, n])
    for i, j in links:
        A[i, j] += 1
        A[j, i] += 1
    triangles = H_int.edges.filterby("size", 3).members()
    B = np.zeros([n, n, n])
    for t in triangles:
        for i, j, k in product(t, repeat=3):
            B[i, j, k] += 1

I'm p sure that with some advanced slicing you could set these entries of A and B in a single line with no need of loops.

        r2 = np.zeros(n, dtype=complex)
        r1 = A.dot(np.exp(1j*theta))
        r2 = np.exp(-1j*theta).dot(B).dot(np.exp(2j*theta))

There's no need for the double definition of r2. The line r2 = np.zeros(n, dtype=complex) is not necessary (unless I' missing something?)

@saad1282
Copy link
Contributor Author

saad1282 commented Sep 8, 2022

Thank you for your contribution @saad1282 ! I left a few minor comments that hopefully won't be too time-consuming to address.

The algorithm it self looks good to me. It's clean and easy to read. However I'm a bit concerned about performance. I assume the operations inside the main loop are hard to vectorize since they iterate over the links/triangles, is that correct? Or are you aware of some way of writing down these operations using matrices? If we can get rid of those inner loops and write the entire computation in a single/few matrix computations then we'd gain a lot in performance.

@leotrs This is a good point. This is now issue #167.

@nwlandry nwlandry merged commit 7504098 into xgi-org:main Sep 8, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants