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]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010

[2]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[3]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[4]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020273

[5]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049

[6]

Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467

[7]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075

[8]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[9]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[10]

Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447

[11]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[12]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[13]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

 Impact Factor: 

Metrics

  • PDF downloads (146)
  • HTML views (1755)
  • Cited by (0)

Other articles
by authors

[Back to Top]