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]

Hengrui Luo, Alice Patania, Jisu Kim, Mikael Vejdemo-Johansson. Generalized penalty for circular coordinate representation. Foundations of Data Science, 2021, 3 (4) : 729-767. doi: 10.3934/fods.2021024

[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]

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

[4]

Niclas Kruff, Sebastian Walcher. Coordinate-independent criteria for Hopf bifurcations. Discrete and Continuous Dynamical Systems - S, 2020, 13 (4) : 1319-1340. doi: 10.3934/dcdss.2020075

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

Kengo Nakai, Yoshitaka Saiki. Machine-learning construction of a model for a macroscopic fluid variable using the delay-coordinate of a scalar observable. Discrete and Continuous Dynamical Systems - S, 2021, 14 (3) : 1079-1092. doi: 10.3934/dcdss.2020352

[11]

Eva Ahbe, Andrea Iannelli, Roy S. Smith. A novel moving orthonormal coordinate-based approach for region of attraction analysis of limit cycles. Journal of Computational Dynamics, 2022  doi: 10.3934/jcd.2022016

[12]

Zhiping Zhou, Yao Yin, Mi Zhou, Hao Cheng, Panos M. Pardalos. Equity-based incentive to coordinate shareholder-manager interests under information asymmetry. Journal of Industrial and Management Optimization, 2022, 18 (6) : 4447-4470. doi: 10.3934/jimo.2021167

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Meng Zhao. The longtime behavior of the model with nonlocal diffusion and free boundaries in online social networks. Electronic Research Archive, 2020, 28 (3) : 1143-1160. doi: 10.3934/era.2020063

[20]

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 and Games, 2016, 3 (2) : 191-216. doi: 10.3934/jdg.2016010

 Impact Factor: 

Metrics

  • PDF downloads (518)
  • HTML views (1821)
  • Cited by (0)

Other articles
by authors

[Back to Top]