February 2018, 1(1): 1-10. doi: 10.3934/mfc.2018001

Network(graph) data research in the coordinate system

1. 

College of Information Science and Technology, Beijing Normal University, Beijing 100875, China

2. 

School of Computer Science, Anhui University of Technology, Maanshan 243002, China

* Corresponding author: linzhi

Received  October 2017 Revised  December 2017 Published  February 2018

Many approaches have been proposed to perform the analysis of network(graph) data correlated with Internet, social networks, communication networks, knowledge graph etc, but few of them have been applied in the coordinate system which is thought to be an efficient platform to processing graph data. In this survey, we provide a short yet structured analysis of network(graph) data research in the coordinate system. We first introduce the coordinate embedding and transforming of double-loop network with its symmetrical and regular structure. We then present two categories of approaches for Internet embedding in the coordinate system and the technology of graph embedding of social network. Finally, we draw our conclusions and discuss potential applications and future research direction.

Citation: Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001
References:
[1] C. C. Aggarwal and H. Wang, Managing and Mining Graph Data, Springer-Verlag, New York, 2010.
[2]

Y. ChenY. Li and T. Chen, Optimal fault-tolerant routing algorithm and fault-tolerant diameter in directed double-loop networks, Theoretical Computer Science., 468 (2013), 50-58. doi: 10.1016/j.tcs.2012.11.008.

[3]

D. B. ChenL. Lu and M. S. Shang, Identifying influential nodes in complex networks, Physica A., (2012), 1777-1787.

[4]

M. CostaM. CastroA. Rowstron and P. Key, Pic:Practical internet coordinates for distance estimation, In Proc.of ICDCS., (2004), 178-187.

[5]

F. DabekR. CoxF. Kaashoek and R. Morris, Vivaldi: A decentralized network coordinate system, In Proc.of SIGCOMM., (2004), 15-26.

[6]

H. P. Dharmasena and X. Yan, An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks, IEEE Trans on Parallel and Ditributed Systems, 16 (2005), 841-852. doi: 10.1109/TPDS.2005.103.

[7]

B. DonnetB. Gueye and M. A. Kaafar, A survey on network coordinates systems, design, and security, IEEE Communication Surveys and Tutorials, 12 (2010), 488-503. doi: 10.1109/SURV.2010.032810.00007.

[8]

A. A. Farrag, Developing fault-tolerant distributed loops, Information Processing Letters, 111 (2010), 97-101. doi: 10.1016/j.ipl.2010.10.002.

[9]

P. Goyal and E. Ferrara, Graph Embedding Techniques, Applications, and Performance: A Survey, IEEE Trans. on Pattern Analysis and Machine Intelligence, 2017.

[10]

H. LiuZ. Zhang and M. Y. Fang, Research on optimal parallel routing and wide diameter of unidirectional double-loop networks, Journal on Communications, 8 (2014), 63-70.

[11]

F. K. Hwang, A complementary survey on double-loop networks, Theoretical Computer Science, 263 (2001), 211-229. doi: 10.1016/S0304-3975(00)00243-7.

[12]

R. JinY. XiangN. Ruan and D. Fuhry, 3-HOP: A high-compression indexing seheme for reachability query, In Proc.of SIGMOD, (2009), 813-826.

[13]

J. Ledlie, P. Gardner and M. Seltzer, Network Coordinates in the Wild, In Proc. of NSDI, 2007.

[14]

Y. L. LiuY. L. Wang and D. J. Guan, An Optimal Fault-Tolerant Routing Algorithm for Double-Loop Networks, IEEE Trans.on Computers, 50 (2001), 500-505. doi: 10.1109/12.926162.

[15]

J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313. doi: 10.1093/comjnl/7.4.308.

[16]

M. PiasJ. CrowcroftS. WilburT. Harris and S. Bhatti, Lighthouses for scalable distributed location, In Proc.of IPTPS, (2003), 278-291. doi: 10.1007/978-3-540-45172-3_26.

[17]

M. PotamiasF. BonchiC. Castillo and A. Gionis, Fast shortest path distance estimation in large networks, In Proc.of CIKM, (2009), 867-876. doi: 10.1145/1645953.1646063.

[18]

Z. QiY. XiaoB. Shao and H. Wang, Fast and scalable analysis of massive social graphs, In Proc.of VLDB, (2013), 61-72.

[19]

X. L. Ren and L. Y. Lu, Review of ranking nodes in complex networks, Chinese Science Bulletin, 13 (2014), 1175-1197.

[20]

N. Tse and H. Zhang, Predicting internet network distance with coordinates-based approaches, In Proc.of INFOCOM, (2002), 170-179.

[21]

F. Wei, TEDI: Efficient shortest path query answering on graphs, In Proc.of SIGMOD, (2010), 99-110. doi: 10.1145/1807167.1807181.

[22]

C. K. Wong and D. Coppersmith, A combinatorial problem related to multi-module memory organizations, Association for Computing Machinery, 21 (1974), 392-402. doi: 10.1145/321832.321838.

[23]

Y. XiaoW. WuJ. PeiW. Wang and Z. He, Efficiently indexing shortest path by exploiting symmetry in graphs, In Proc.of EDBT, (2009), 493-504. doi: 10.1145/1516360.1516418.

[24]

X. Zhao, A. Sala, C. Wilson, H. Zheng and B. Y. Zhao, Shortest path estimation for large social graphs, In Proc. of WOSN, 2010.

[25]

X. Zhao, A. Sala, H. Zheng and B. Y. Zhao, Fast and scalable analysis of massive social graphs, In Proc. of CORR, 2011.

[26]

X. ZhaoA. ChangA. Sarma and B. Y. Zhao, On the embeddability of random walk distances, In Proc.of VLDB, 6 (2013), 1690-1701. doi: 10.14778/2556549.2556554.

[27]

J. Q. Zhou and X. R. Xu, On infinite families of optimal double-loop networks with non-unit steps, Ars Combinatoria, 97A (2010), 81-95.

show all references

References:
[1] C. C. Aggarwal and H. Wang, Managing and Mining Graph Data, Springer-Verlag, New York, 2010.
[2]

Y. ChenY. Li and T. Chen, Optimal fault-tolerant routing algorithm and fault-tolerant diameter in directed double-loop networks, Theoretical Computer Science., 468 (2013), 50-58. doi: 10.1016/j.tcs.2012.11.008.

[3]

D. B. ChenL. Lu and M. S. Shang, Identifying influential nodes in complex networks, Physica A., (2012), 1777-1787.

[4]

M. CostaM. CastroA. Rowstron and P. Key, Pic:Practical internet coordinates for distance estimation, In Proc.of ICDCS., (2004), 178-187.

[5]

F. DabekR. CoxF. Kaashoek and R. Morris, Vivaldi: A decentralized network coordinate system, In Proc.of SIGCOMM., (2004), 15-26.

[6]

H. P. Dharmasena and X. Yan, An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks, IEEE Trans on Parallel and Ditributed Systems, 16 (2005), 841-852. doi: 10.1109/TPDS.2005.103.

[7]

B. DonnetB. Gueye and M. A. Kaafar, A survey on network coordinates systems, design, and security, IEEE Communication Surveys and Tutorials, 12 (2010), 488-503. doi: 10.1109/SURV.2010.032810.00007.

[8]

A. A. Farrag, Developing fault-tolerant distributed loops, Information Processing Letters, 111 (2010), 97-101. doi: 10.1016/j.ipl.2010.10.002.

[9]

P. Goyal and E. Ferrara, Graph Embedding Techniques, Applications, and Performance: A Survey, IEEE Trans. on Pattern Analysis and Machine Intelligence, 2017.

[10]

H. LiuZ. Zhang and M. Y. Fang, Research on optimal parallel routing and wide diameter of unidirectional double-loop networks, Journal on Communications, 8 (2014), 63-70.

[11]

F. K. Hwang, A complementary survey on double-loop networks, Theoretical Computer Science, 263 (2001), 211-229. doi: 10.1016/S0304-3975(00)00243-7.

[12]

R. JinY. XiangN. Ruan and D. Fuhry, 3-HOP: A high-compression indexing seheme for reachability query, In Proc.of SIGMOD, (2009), 813-826.

[13]

J. Ledlie, P. Gardner and M. Seltzer, Network Coordinates in the Wild, In Proc. of NSDI, 2007.

[14]

Y. L. LiuY. L. Wang and D. J. Guan, An Optimal Fault-Tolerant Routing Algorithm for Double-Loop Networks, IEEE Trans.on Computers, 50 (2001), 500-505. doi: 10.1109/12.926162.

[15]

J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313. doi: 10.1093/comjnl/7.4.308.

[16]

M. PiasJ. CrowcroftS. WilburT. Harris and S. Bhatti, Lighthouses for scalable distributed location, In Proc.of IPTPS, (2003), 278-291. doi: 10.1007/978-3-540-45172-3_26.

[17]

M. PotamiasF. BonchiC. Castillo and A. Gionis, Fast shortest path distance estimation in large networks, In Proc.of CIKM, (2009), 867-876. doi: 10.1145/1645953.1646063.

[18]

Z. QiY. XiaoB. Shao and H. Wang, Fast and scalable analysis of massive social graphs, In Proc.of VLDB, (2013), 61-72.

[19]

X. L. Ren and L. Y. Lu, Review of ranking nodes in complex networks, Chinese Science Bulletin, 13 (2014), 1175-1197.

[20]

N. Tse and H. Zhang, Predicting internet network distance with coordinates-based approaches, In Proc.of INFOCOM, (2002), 170-179.

[21]

F. Wei, TEDI: Efficient shortest path query answering on graphs, In Proc.of SIGMOD, (2010), 99-110. doi: 10.1145/1807167.1807181.

[22]

C. K. Wong and D. Coppersmith, A combinatorial problem related to multi-module memory organizations, Association for Computing Machinery, 21 (1974), 392-402. doi: 10.1145/321832.321838.

[23]

Y. XiaoW. WuJ. PeiW. Wang and Z. He, Efficiently indexing shortest path by exploiting symmetry in graphs, In Proc.of EDBT, (2009), 493-504. doi: 10.1145/1516360.1516418.

[24]

X. Zhao, A. Sala, C. Wilson, H. Zheng and B. Y. Zhao, Shortest path estimation for large social graphs, In Proc. of WOSN, 2010.

[25]

X. Zhao, A. Sala, H. Zheng and B. Y. Zhao, Fast and scalable analysis of massive social graphs, In Proc. of CORR, 2011.

[26]

X. ZhaoA. ChangA. Sarma and B. Y. Zhao, On the embeddability of random walk distances, In Proc.of VLDB, 6 (2013), 1690-1701. doi: 10.14778/2556549.2556554.

[27]

J. Q. Zhou and X. R. Xu, On infinite families of optimal double-loop networks with non-unit steps, Ars Combinatoria, 97A (2010), 81-95.

Figure 1.  Directed DLN G(8; 2, 3)
Figure 2.  embedding graph of G(8;2, 3)
Figure 3.  Coordinates transforming of node u in G(N; r, s)
Figure 4.  MDD of G(39;$\pm$1, $\pm$17) & G(39;1, 17)
Figure 5.  Coordinates embedding and transforming of nodes on axes & G(39; 1, 17)
Figure 6.  Geometric space model of the Internet
Figure 7.  triangle inequality violations (TIV)
Figure 8.  Mapping graph nodes into Euclidean coordinate system
Figure 9.  Architecture of a coordinate-based distance oracle
[1]

Jianlu Zhang. Suspension of the billiard maps in the Lazutkin's coordinate. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 2227-2242. doi: 10.3934/dcds.2017096

[2]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487

[3]

Werner Creixell, Juan Carlos Losada, Tomás Arredondo, Patricio Olivares, Rosa María Benito. Serendipity in social networks. Networks & Heterogeneous Media, 2012, 7 (3) : 363-371. doi: 10.3934/nhm.2012.7.363

[4]

Sharon M. Cameron, Ariel Cintrón-Arias. Prisoner's Dilemma on real social networks: Revisited. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1381-1398. doi: 10.3934/mbe.2013.10.1381

[5]

Robin Cohen, Alan Tsang, Krishna Vaidyanathan, Haotian Zhang. Analyzing opinion dynamics in online social networks. Big Data & Information Analytics, 2016, 1 (4) : 279-298. doi: 10.3934/bdia.2016011

[6]

Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks & Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295

[7]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201

[8]

Guowei Dai, Ruyun Ma, Haiyan Wang, Feng Wang, Kuai Xu. Partial differential equations with Robin boundary condition in online social networks. Discrete & Continuous Dynamical Systems - B, 2015, 20 (6) : 1609-1624. doi: 10.3934/dcdsb.2015.20.1609

[9]

Lea Ellwardt, Penélope Hernández, Guillem Martínez-Cánovas, Manuel Muñoz-Herrera. Conflict and segregation in networks: An experiment on the interplay between individual preferences and social influence. Journal of Dynamics & Games, 2016, 3 (2) : 191-216. doi: 10.3934/jdg.2016010

[10]

Yi Xu, Qing Yang, Dianhui Chu. Exploring timeliness for accurate recommendation in location-based social networks. Mathematical Foundations of Computing, 2018, 1 (1) : 11-48. doi: 10.3934/mfc.2018002

[11]

Jingli Ren, Dandan Zhu, Haiyan Wang. Spreading-vanishing dichotomy in information diffusion in online social networks with intervention. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-23. doi: 10.3934/dcdsb.2018240

[12]

Maya Mincheva, Gheorghe Craciun. Graph-theoretic conditions for zero-eigenvalue Turing instability in general chemical reaction networks. Mathematical Biosciences & Engineering, 2013, 10 (4) : 1207-1226. doi: 10.3934/mbe.2013.10.1207

[13]

Randall Dougherty and Thomas Jech. Left-distributive embedding algebras. Electronic Research Announcements, 1997, 3: 28-37.

[14]

Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017

[15]

Pradeep Dubey, Rahul Garg, Bernard De Meyer. Competing for customers in a social network. Journal of Dynamics & Games, 2014, 1 (3) : 377-409. doi: 10.3934/jdg.2014.1.377

[16]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[17]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17

[18]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[19]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[20]

Benoît Perthame, Delphine Salort. On a voltage-conductance kinetic system for integrate & fire neural networks. Kinetic & Related Models, 2013, 6 (4) : 841-864. doi: 10.3934/krm.2013.6.841

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]