Scribd Logo
Upload

Welcome to Scribd!

  • 36 views

    Ec614 Assignment (Dynamics, Learning, and Security in Network Systems)

    Uploaded by

    vahape
    The document describes simulating an agreement protocol on graphs with different numbers of edges. It shows that: 1) In general, increasing the number of edges increases connectivity and the Laplacian eigenvalues, leading to faster convergence. 2) However, there is a limit, as once a graph is fully connected additional edges do not help. 3) Adding edges between previously unconnected nodes helps, but redundant edges may not and could even slow convergence. 4) Simulation examples demonstrate that more edges do not always improve convergence - it can also worsen it in some cases.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Ec614 Assignment (Dynamics, Learning, and Security in Network Systems)

    Uploaded by

    vahape
    36 views10 pages
    The document describes simulating an agreement protocol on graphs with different numbers of edges. It shows that: 1) In general, increasing the number of edges increases connectivity and the Laplacian eigenvalues, leading to faster convergence. 2) However, there is a limit, as once a graph is fully connected additional edges do not help. 3) Adding edges between previously unconnected nodes helps, but redundant edges may not and could even slow convergence. 4) Simulation examples demonstrate that more edges do not always improve convergence - it can also worsen it in some cases.

    Original Title

    Untitled

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes simulating an agreement protocol on graphs with different numbers of edges. It shows that: 1) In general, increasing the number of edges increases connectivity and the Laplacian eigenvalues, leading to faster convergence. 2) However, there is a limit, as once a graph is fully connected additional edges do not help. 3) Adding edges between previously unconnected nodes helps, but redundant edges may not and could even slow convergence. 4) Simulation examples demonstrate that more edges do not always improve convergence - it can also worsen it in some cases.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    36 views10 pages

    Ec614 Assignment (Dynamics, Learning, and Security in Network Systems)

    Uploaded by

    vahape
    The document describes simulating an agreement protocol on graphs with different numbers of edges. It shows that: 1) In general, increasing the number of edges increases connectivity and the Laplacian eigenvalues, leading to faster convergence. 2) However, there is a limit, as once a graph is fully connected additional edges do not help. 3) Adding edges between previously unconnected nodes helps, but redundant edges may not and could even slow convergence. 4) Simulation examples demonstrate that more edges do not always improve convergence - it can also worsen it in some cases.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 10

    EC614 ASSIGNMENT

    (Dynamics,Learning, and
    Security in Network Systems)

    Name : Prajakta Bisaria


    Roll No: 1901140
    Aim: Simulate the agreement protocol dx(t)/dt=-L(G)x(t)
    for an undirected graph on five vertices. Compare the rate
    of convergence of the protocol as the number of edges
    increases. Does the convergence of the protocol always
    improve when the graph contains more edges? Provide an
    analysis to support your observation.

    Solution

    Below MATLAB code simulates an agreement protocol


    governed by the differential equation dx(t)/dt = - L(G)x(t),
    where L(G) is the Laplacian matrix of a five-node undirected
    graph.

    First the adjacency matrix of the graph is defined


    A = [0 1 0 0 1;
    1 0 1 0 0;
    0 1 0 1 0;
    0 0 1 0 1;
    1 0 0 1 0];

    Then Computing the degree


    matrix
    D = diag(sum(A));
    then Computing the Laplacian
    matrix
    L = D - A;

    Set the initial condition for the


    protocol
    x0 = [1; 2; 3; 4; 5];

    Set the simulation


    time
    tspan = [0 10];

    Then defining the function dxdt


    dx/dt = -L(G)x(t), which is simply -Lx.
    dxdt = @(t, x) -L*x;

    Finally, we use the ode45 function to solve the differential


    equation numerically and obtain the evolution of the protocol over
    time.
    [t, x] = ode45(dxdt, tspan, x0);

    % Plot the evolution of the protocol


    over time plot(t, x);
    title('Agreement Protocol
    Evolution'); xlabel('Time');
    ylabel('Protocol Value');
    o As the number of edges increases, the connectivity of the
    graph increases .The rate of convergence is determined by
    the second smallest eigen value of the Laplacian matrix.
    o As the number of edges increases, the graph becomes more
    connected, and the Laplacian matrix's eigenvalues become
    larger.
    o Thus, if we increase the number of edges in the graph, we
    would expect the second smallest eigenvalue to increase
    (assuming the graph remains connected). This would in turn
    lead to faster convergence of the agreement protocol.

    o Below is the example of four graphs connected with


    different number of edges and thus find out the Laplacian
    matrix of all the graph and simulated it one by one to show
    the convergence rate

    L1 = [2, -1, -1, 0, 0;


    -1, 2, 0, -1, 0;
    -1, 0, 2, -1, 0;
    0, -1, -1, 3, -1;
    0, 0, 0, -1, 1];

    L2 = [2, -1, 0, -1, 0;


    -1, 3, -1, -1, 0;
    0, -1, 2, 0, -1;
    -1, -1, 0, 3, -1;
    0, 0, -1, -1, 2];

    L3 = [2, -1, 0, 0, -1;


    -1, 2, -1, 0, 0;
    0, -1, 2, -1, 0;
    0, 0, -1, 2, -1;
    -1, 0, 0, -1, 2];

    L4 = [3, -1, -1, -1, 0;


    -1, 2, 0, 0, -1;
    -1, 0, 2, 0, -1;
    -1, 0, 0, 2, -1;
    0, -1, -1, -1, 3];
    % Set the initial condition for the protocol
    x0 = [2; 5; 12; 20; 25];

    % Set the simulation time


    tspan = [0 10];

    % Define the function for the protocol


    dxdt1 = @(t, x) -L1*x;
    dxdt2 = @(t, x) -L2*x;
    dxdt3 = @(t, x) -L3*x;
    dxdt4 = @(t, x) -L4*x;

    % Solve the differential equation numerically


    [t1, x1] = ode45(dxdt1, tspan, x0);
    [t2, x2] = ode45(dxdt2, tspan, x0);
    [t3, x3] = ode45(dxdt3, tspan, x0);
    [t4, x4] = ode45(dxdt4, tspan, x0);

    % Plot the evolution of the protocol over time


    figure(1)
    plot(t1, x1);
    title('Agreement Protocol Evolution');
    xlabel('Time');
    ylabel('Protocol Value');

    figure(2)
    plot(t2, x2);
    title('Agreement Protocol Evolution');
    xlabel('Time');
    ylabel('Protocol Value');

    figure(3)
    plot(t3, x3);
    title('Agreement Protocol Evolution');
    xlabel('Time');
    ylabel('Protocol Value');

    figure(4)
    plot(t4, x4);
    title('Agreement Protocol Evolution');
    xlabel('Time');
    ylabel('Protocol Value');
    Fig 1

    Fig 2
    Fig 3

    Fig 4
    Increasing the number of edges generally leads to faster
    convergence of the agreement protocol, as it increases the graph's
    connectivity and the Laplacian matrix's eigenvalues. However,
    there is a limit to how much we can increase the connectivity of
    the graph by adding edges, and once the graph becomes fully
    connected, the convergence rate reaches its maximum value.

    But, adding more edges to a graph does not always improve the
    convergence of the agreement protocol. In general, adding edges
    that connect previously unconnected nodes can improve the
    convergence rate, as this increases the connectivity of the graph
    and can lead to faster information exchange among the nodes.
    However, adding redundant edges or loops to the graph may not
    improve convergence and can even worsen it.

    To show it we take two graph and simulate it to show that


    increasing the edge does not always improve the convergence but
    can also worsen it:

    L1 = [ 2 -1 0 0 -1 ;
    -1 3 -1 0 -1 ;
    0 -1 2 -1 0 ;
    0 0 -1 2 -1 ;
    -1 -1 0 -1 3 ];

    L2 = [ 3 -1 -1 0 -1 ;
    -1 3 -1 0 -1 ;
    -1 -1 4 -1 -1 ;
    0 0 -1 3 -1 ;
    -1 -1 -1 -1 4 ];

    % Set the initial condition for the protocol


    x0 = [2; 5; 12; 20; 25];

    % Set the simulation time


    tspan = [0 35];

    % Define the function for the protocol


    dxdt1 = @(t, x) -L1*x;
    dxdt2 = @(t, x) -L2*x;
    % Solve the differential equation numerically
    [t1, x1] = ode45(dxdt1, tspan, x0);
    [t2, x2] = ode45(dxdt2, tspan, x0);

    % Plot the evolution of the protocol over time


    figure(1)
    plot(t1, x1);
    title('Agreement Protocol Evolution');
    xlabel('Time');
    ylabel('Protocol Value');

    figure(2)
    plot(t2, x2);
    title('Agreement Protocol Evolution');
    xlabel('Time');
    ylabel('Protocol Value');

    Fig 5
    Fig 6

    The simulation plot shows that as the number of edges is increased in


    graph above, the convergence of the system does not improve but
    instead deteriorates.

    You might also like