Sridhar Ramasamy

M.S. FinalJan 30, 2017, 9:00 am - 11:00 am

LSC 304

Capture & Reconstruction of the Topology of Undirected Graphs with Partial Coordinates: A Matrix Completion based Approach

Abstract: With the advancement in science and technology, new types of complex networks have become common place across varied domains such as

computer networks, Internet, bio-technological studies, sociology and condensed matter physics. The surge of interest in research towards graph and

topology can be attributed to important applications such as representing networks of communication, graph representation of words in computational

linguistics, in identification of terrorists for national security, studying complicated atomic structures and connectivity in condensed matter physics. Well-

known social networks, Facebook and twitter, have millions of users, while the science citation index is a repository of millions of records and citations.

These examples indicate the importance of efficient techniques for measuring, characterizing and mining large and complex networks.

Often analysis of graph attributes to understand the graph topology and embedded properties on these complex graphs becomes difficult due to

causes such as huge data volumes for processing, lack of compressed representation forms and lack of complete information. Due to improper or

inadequate acquiring processes, inaccessibility, etc., often we end up with partial graph representational data. Thus there is immense significance in

being able to extract this missing information from available data. Therefore obtaining the topology of a graph, such as a communication network or a

social network from incomplete information is our research focus. Specifically, this research addresses the problem of capturing and reconstructing the

topology of a network from a small set of path length measurements. An accurate solution for this problem also provides means of describing graphs

with a compressed representation.

A technique to obtain the topology from only a partial set of information about network paths is presented. Specifically, we demonstrate the capture of

the network topology from a small set of measurements corresponding to a) shortest hop distances of nodes with respect to small set of nodes called

as anchors, or b) a set of pairwise hop distances between random node pairs. These two measurement sets can be related to the Distance matrix D, a

common representation of the topology, where an entry contains the shortest hop distance between two nodes. In an anchor based method, the

shortest hop distances of nodes to a set of M anchors constitute what is known as a Virtual Coordinate (VC) matrix. This is a sub-matrix of columns of

D corresponding to the anchor nodes. Random pairwise measurements correspond to a random subset of elements of D. The proposed technique

depends on a low rank matrix completion method based on extended Robust Principal Component Analysis to extract the unknown elements.

The application of the principles of matrix completion relies on the conjecture that many natural data sets are inherently low dimensional and thus

corresponding matrix is relatively low ranked. We demonstrate that this is applicable to D of many large-scale networks as well. Thus we are able to

use results from the theory of matrix completion for capturing the topology.

Two important types of graphs have been used for evaluation of the proposed technique, namely, Wireless Sensor Network (WSN) graphs and social

network graphs. For WSN examples, we use the Topology Preserving Map (TPM), which is a homeomorphic representation of the original layout, to

evaluate the effectiveness of the technique from partial sets of entries of VC matrix. A double centering based approach is used to evaluate the TPMs

from VCs, in comparison with the existing non-centered approach. Results are presented for both random anchors and nodes that are farthest apart on

the boundaries.

The idea of obtaining topology is extended towards social network link prediction. The significance of this result lies in the fact that with increasing

privacy concerns, obtaining the data in the form of VC matrix or as hop distance matrix becomes difficult. This approach of predicting the unknown

entries of a matrix provides a novel approach for social network link predictions, and is supported by the fact that the distance matrices of most real

world networks are naturally low ranked.

The accuracy of the proposed techniques is evaluated using 4 different WSN and 3 different social networks. Two 2D and two 3D networks have been

used for WSNs with the number of nodes ranging from 500 to 1600. We are able to obtain accurate TPMs for both random anchors and extreme

anchors with only 20% to 40% of VC matrix entries. The mean error quantifies the error introduced in TPMs due to unknown entries. The results

indicate that even with 80% of entries missing, the mean error is around 35% to 45%.

The Facebook, Collaboration and Enron Email sub networks, with 744, 4158 and 3892 nodes respectively, have been used for social network capture.

The results obtained are very promising. With 80% of information missing in the hop-distance matrix, a maximum error of only around 6% is incurred.

The error in prediction of hop distance is less than 0.5 hops. This has also opened up the idea of compressed representation of networks by its VC

matrix.

computer networks, Internet, bio-technological studies, sociology and condensed matter physics. The surge of interest in research towards graph and

topology can be attributed to important applications such as representing networks of communication, graph representation of words in computational

linguistics, in identification of terrorists for national security, studying complicated atomic structures and connectivity in condensed matter physics. Well-

known social networks, Facebook and twitter, have millions of users, while the science citation index is a repository of millions of records and citations.

These examples indicate the importance of efficient techniques for measuring, characterizing and mining large and complex networks.

Often analysis of graph attributes to understand the graph topology and embedded properties on these complex graphs becomes difficult due to

causes such as huge data volumes for processing, lack of compressed representation forms and lack of complete information. Due to improper or

inadequate acquiring processes, inaccessibility, etc., often we end up with partial graph representational data. Thus there is immense significance in

being able to extract this missing information from available data. Therefore obtaining the topology of a graph, such as a communication network or a

social network from incomplete information is our research focus. Specifically, this research addresses the problem of capturing and reconstructing the

topology of a network from a small set of path length measurements. An accurate solution for this problem also provides means of describing graphs

with a compressed representation.

A technique to obtain the topology from only a partial set of information about network paths is presented. Specifically, we demonstrate the capture of

the network topology from a small set of measurements corresponding to a) shortest hop distances of nodes with respect to small set of nodes called

as anchors, or b) a set of pairwise hop distances between random node pairs. These two measurement sets can be related to the Distance matrix D, a

common representation of the topology, where an entry contains the shortest hop distance between two nodes. In an anchor based method, the

shortest hop distances of nodes to a set of M anchors constitute what is known as a Virtual Coordinate (VC) matrix. This is a sub-matrix of columns of

D corresponding to the anchor nodes. Random pairwise measurements correspond to a random subset of elements of D. The proposed technique

depends on a low rank matrix completion method based on extended Robust Principal Component Analysis to extract the unknown elements.

The application of the principles of matrix completion relies on the conjecture that many natural data sets are inherently low dimensional and thus

corresponding matrix is relatively low ranked. We demonstrate that this is applicable to D of many large-scale networks as well. Thus we are able to

use results from the theory of matrix completion for capturing the topology.

Two important types of graphs have been used for evaluation of the proposed technique, namely, Wireless Sensor Network (WSN) graphs and social

network graphs. For WSN examples, we use the Topology Preserving Map (TPM), which is a homeomorphic representation of the original layout, to

evaluate the effectiveness of the technique from partial sets of entries of VC matrix. A double centering based approach is used to evaluate the TPMs

from VCs, in comparison with the existing non-centered approach. Results are presented for both random anchors and nodes that are farthest apart on

the boundaries.

The idea of obtaining topology is extended towards social network link prediction. The significance of this result lies in the fact that with increasing

privacy concerns, obtaining the data in the form of VC matrix or as hop distance matrix becomes difficult. This approach of predicting the unknown

entries of a matrix provides a novel approach for social network link predictions, and is supported by the fact that the distance matrices of most real

world networks are naturally low ranked.

The accuracy of the proposed techniques is evaluated using 4 different WSN and 3 different social networks. Two 2D and two 3D networks have been

used for WSNs with the number of nodes ranging from 500 to 1600. We are able to obtain accurate TPMs for both random anchors and extreme

anchors with only 20% to 40% of VC matrix entries. The mean error quantifies the error introduced in TPMs due to unknown entries. The results

indicate that even with 80% of entries missing, the mean error is around 35% to 45%.

The Facebook, Collaboration and Enron Email sub networks, with 744, 4158 and 3892 nodes respectively, have been used for social network capture.

The results obtained are very promising. With 80% of information missing in the hop-distance matrix, a maximum error of only around 6% is incurred.

The error in prediction of hop distance is less than 0.5 hops. This has also opened up the idea of compressed representation of networks by its VC

matrix.

Adviser: Dr Anura Jayasumana

Co-Adviser: N/A

Non-ECE Member: Dr Indrajit Ray, CS dept.

Member 3: Dr Sudeep Pasricha, ECE dept.

Addional Members: Dr Randy Paffenroth, ECE dept.

Co-Adviser: N/A

Non-ECE Member: Dr Indrajit Ray, CS dept.

Member 3: Dr Sudeep Pasricha, ECE dept.

Addional Members: Dr Randy Paffenroth, ECE dept.

Publications:

1) A.P. Jayasumana, R. Paffenroth, S. Ramasamy, "Topology Maps and Distance Free Localization from Partial Virtual Coordinates for IoT,"Â Â Â Proc. IEEE Communications Conference - SAC5-IOT,Â (ICC2016), Kuala Lumpur, Malaysia, May 2016.

2) R.Paffenroth, A.P.Jayasumana, S. Ramasamy , â€œNetwork Topology Mapping from Graph Geodesics and Partial Virtual Coordinatesâ€ (in preparation)

3) S. Ramasamy, R.Paffenroth, A.P.Jayasumana, â€œA Low Complexity Technique for Capture and Characterization of Social Network Topologyâ€ (in preparation)

1) A.P. Jayasumana, R. Paffenroth, S. Ramasamy, "Topology Maps and Distance Free Localization from Partial Virtual Coordinates for IoT,"Â Â Â Proc. IEEE Communications Conference - SAC5-IOT,Â (ICC2016), Kuala Lumpur, Malaysia, May 2016.

2) R.Paffenroth, A.P.Jayasumana, S. Ramasamy , â€œNetwork Topology Mapping from Graph Geodesics and Partial Virtual Coordinatesâ€ (in preparation)

3) S. Ramasamy, R.Paffenroth, A.P.Jayasumana, â€œA Low Complexity Technique for Capture and Characterization of Social Network Topologyâ€ (in preparation)

Program of Study:

ECE 512 - Digital Signal Processing

ECE 514 - Applications of Random Processing

ECE 516 - Information Theory

ECE 554 â€“ Computer Architecture

ECE 658 â€“ Internet Engineering

CS 556 â€“ Computer Security

MATH 560 â€“ Linear Algebra

N/A

ECE 512 - Digital Signal Processing

ECE 514 - Applications of Random Processing

ECE 516 - Information Theory

ECE 554 â€“ Computer Architecture

ECE 658 â€“ Internet Engineering

CS 556 â€“ Computer Security

MATH 560 â€“ Linear Algebra

N/A