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.   Google Scholar
[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.  Google Scholar

[3]

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

[4]

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

[5]

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

[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.  Google Scholar

[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.  Google Scholar

[8]

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

[9]

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

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[19]

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

[20]

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

[21]

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

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[25]

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

[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.  Google Scholar

[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.   Google Scholar

show all references

References:
[1] C. C. Aggarwal and H. Wang, Managing and Mining Graph Data, Springer-Verlag, New York, 2010.   Google Scholar
[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.  Google Scholar

[3]

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

[4]

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

[5]

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

[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.  Google Scholar

[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.  Google Scholar

[8]

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

[9]

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

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[19]

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

[20]

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

[21]

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

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[25]

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

[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.  Google Scholar

[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.   Google Scholar

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]

Luca Consolini, Alessandro Costalunga, Manfredi Maggiore. A coordinate-free theory of virtual holonomic constraints. Journal of Geometric Mechanics, 2018, 10 (4) : 467-502. doi: 10.3934/jgm.2018018

[3]

Niclas Kruff, Sebastian Walcher. Coordinate-independent criteria for Hopf bifurcations. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1-15. doi: 10.3934/dcdss.2020075

[4]

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

[5]

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

[6]

Yuki Kumagai. Social networks and global transactions. Journal of Dynamics & Games, 2019, 6 (3) : 211-219. doi: 10.3934/jdg.2019015

[7]

Xumin Jiang. Isometric embedding with nonnegative Gauss curvature under the graph setting. Discrete & Continuous Dynamical Systems - A, 2019, 39 (6) : 3463-3477. doi: 10.3934/dcds.2019143

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Xiaoshuang Xing, Gaofei Sun, Yong Jin, Wenyi Tang, Xiuzhen Cheng. Relay selection based on social relationship prediction and information leakage reduction for mobile social networks. Mathematical Foundations of Computing, 2018, 1 (4) : 369-382. doi: 10.3934/mfc.2018018

[13]

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

[14]

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

[15]

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

[16]

Jingli Ren, Dandan Zhu, Haiyan Wang. Spreading-vanishing dichotomy in information diffusion in online social networks with intervention. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1843-1865. doi: 10.3934/dcdsb.2018240

[17]

Serap Ergün, Bariş Bülent Kırlar, Sırma Zeynep Alparslan Gök, Gerhard-Wilhelm Weber. An application of crypto cloud computing in social networks by cooperative game theory. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019036

[18]

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

[19]

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

[20]

Andrea Natale, François-Xavier Vialard. Embedding Camassa-Holm equations in incompressible Euler. Journal of Geometric Mechanics, 2019, 11 (2) : 205-223. doi: 10.3934/jgm.2019011

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]