Network(graph) data research in the coordinate system

Liu Hui; Lin Zhi; Waqas Ahmad

doi:10.3934/mfc.2018001

Article Contents

2018, Volume 1, Issue 1: 1-10. Doi: 10.3934/mfc.2018001

This issue Previous Article Next Article Exploring timeliness for accurate recommendation in location-based social networks

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
^* Corresponding author: linzhi

Received: September 30, 2017

Revised: November 30, 2017

Published: February 2018

Abstract Full Text(HTML) Figure(9) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. Directed DLN G(8; 2, 3)

Download: Full-size image PowerPoint slide

Figure 2. embedding graph of G(8;2, 3)

Download: Full-size image PowerPoint slide

Figure 3. Coordinates transforming of node u in G(N; r, s)

Download: Full-size image PowerPoint slide

Figure 4. MDD of G(39;$\pm$1, $\pm$17) & G(39;1, 17)

Download: Full-size image PowerPoint slide

Figure 5. Coordinates embedding and transforming of nodes on axes & G(39; 1, 17)

Download: Full-size image PowerPoint slide

Figure 6. Geometric space model of the Internet

Download: Full-size image PowerPoint slide

Figure 7. triangle inequality violations (TIV)

Download: Full-size image PowerPoint slide

Figure 8. Mapping graph nodes into Euclidean coordinate system

Download: Full-size image PowerPoint slide

Figure 9. Architecture of a coordinate-based distance oracle

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	C. C. Aggarwal and H. Wang, Managing and Mining Graph Data, Springer-Verlag, New York, 2010.
[2]	Y. Chen, Y. 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. Chen, L. Lu and M. S. Shang, Identifying influential nodes in complex networks, Physica A., (2012), 1777-1787.
[4]	M. Costa, M. Castro, A. Rowstron and P. Key, Pic:Practical internet coordinates for distance estimation, In Proc.of ICDCS., (2004), 178-187.
[5]	F. Dabek, R. Cox, F. 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. Donnet, B. 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. Liu, Z. 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. Jin, Y. Xiang, N. 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. Liu, Y. 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. Pias, J. Crowcroft, S. Wilbur, T. 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. Potamias, F. Bonchi, C. 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. Qi, Y. Xiao, B. 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. Xiao, W. Wu, J. Pei, W. 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. Zhao, A. Chang, A. 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.