Functional dependence graph (FDG) is an important class of directed graph that captures the functional dependence relationships of a set of random variables and it is frequently used in characterising network coding capacity bounds. Since the computational complexity of such bounds usually grows exponentially with the order of the FDG, it is desirable to find an FDG with the smallest size possible. To this end, some systematic graph reduction techniques are introduced in this study. The first reduction technique is performed on the original networks, where ‘non-essential’ edges are identified and eliminated. This is equivalent to node reduction in the corresponding FDG. Besides, the authors show that certain edges in the FDG may also be removed without affecting the functional dependence relationships of the random variables. The removal of the edges in the FDG may create new opportunities to reduce the order of the FDG. It is proved that the reduced FDGs give the same network coding capacity region/bounds as that obtained by using the original FDGs and yet much less computation is required.

References

1. 1)
  - 18. Ho, T., Effros, M., Jalali, S.: ‘On equivalence between network topologies’. 48th Annual Allerton Conf. on Communication, Control and Computing, Monticello, USA, September 2010, pp. 391–398.
2. 2)
  - 20. Song, W., Cai, K., Feng, R., Rui, W.: ‘Solving the two simple multicast network coding problem in time o(|e|)’. Proc. of IEEE Third Int. Conf. on Communication Software and Networks, Xi'an, China, May 2011, pp. 427–431.
3. 3)
  - 11. Kramer, G., Savari, S.: ‘Edge-cut bounds on network coding rates’, J. Netw. Syst. Manage., 2006, 14, pp. 49–67 (doi: 10.1007/s10922-005-9019-0).
4. 4)
  - R. Koetter , M. Medard . An algebraic approach to network coding. IEEE/ACM Trans. Netw. , 5 , 782 - 795
5. 5)
  - 23. Dougherty, R., Freiling, C., Zeger, K.: ‘Unachievability of network coding capacity’, IEEE Trans. Inf. Theory, 2006, 52, pp. 2365–2372 (doi: 10.1109/TIT.2006.874405).
6. 6)
  - 15. Xu, X., Thakor, S., Guan, Y.L.: ‘Reduced functional dependence graphs and their applications’. Proc. of the IEEE Int. Symp. on Network Coding, MIT, Cambridge, MA, June 2012, pp. 61–66.
7. 7)
  - 26. Thakor, S., Grant, A., Chan, T.: ‘On complexity reduction of the lp bound computation and related problems’. Proc. of the IEEE Int. Symp. on Network Coding, Beijing, China, July 2011, pp. 1–6.
8. 8)
  - 22. Dougherty, R., Freiling, C., Zeger, K.: ‘Insufficiency of linear coding in network information flow’, IEEE Trans. Inf. Theory, 2005, 51, pp. 2745–2759 (doi: 10.1109/TIT.2005.851744).
9. 9)
  - 27. Orlitsky, A., Roche, J.R.: ‘Coding for computing’, IEEE Trans. Inf. Theory, 2001, 47, pp. 903–917 (doi: 10.1109/18.915643).
10. 10)
  - 3. Gu, S., Jiao, J., Zhang, Q., Yang, Z., Xiang, W., Cao, B.: ‘Network-coded rateless coding scheme in erasure multiple-access relay enable communications’, IET Commun., 2014, 8, (4), pp. 537–545.
11. 11)
  - M.E.J. Newman . The structure and function of complex networks. SIAM Rev. , 167 - 256
12. 12)
  - 8. Matus, F.: ‘Infinitely many information inequalities’. Proc. 2007 IEEE Int. Symp. Inform. Theory, Nice, France, June 2007, pp. 41–44.
13. 13)
  - 4. Chung, T.Y., Wang, C.C., Chen, Y.M., Chang, Y.H.: ‘PNECOS: a peer-to-peer network coding streaming system’, J. Internet Technol., 2009, 10, (3), pp. 261–270.
14. 14)
  - 10. Kramer, G.: ‘Directed Information for channels with feedback’. Zurich: PhD thesis, Swiss Federal Institute of Technology, 1998.
15. 15)
  - 12. Thakor, S., Grant, A., Chan, T.: ‘Network coding capacity: a functional dependence bound’. Proc. 2009 IEEE Int. Symp. Information Theory, Seoul, Korea, June 2009, pp. 263–267.
16. 16)
  - 7. Yan, X., Yeung, R.W., Zhang, Z.: ‘The capacity region for multi-source multi-sink network coding’. Proc. 2007 IEEE Int. Symp. Inform. Theory, Nice, France, June 2007, pp. 116–120.
17. 17)
  - 17. Koetter, R., Effros, M., Médard, M.: ‘A theory of network equivalence – part ii: Mutltiterminal channels’ (ArXive e-prints, 2010).
18. 18)
  - 19. Gallo, G., Longo, G., Nguyen, S., Pallottino, S.: ‘Directed hypergraphs and applications’, Discrete Appl. Math., 1992, 40, pp. 117–201.
19. 19)
  - 21. Yu, C.W.: ‘Computing subgraph probability of random geometric graphs with applications in quantitative analysis of ad hoc networks’, IEEE J. Sel. A, Commun., 2009, 27, pp. 1056–1065 (doi: 10.1109/JSAC.2009.090904).
20. 20)
  - 6. Han, H., Peng, D., Wang, L.: ‘Upper bounds for the failure probability of random linear network coding for multicast network’, IET Netw., 2013, 2, (4), pp. 181–187 (doi: 10.1049/iet-net.2012.0231).
21. 21)
  - 20. Liu, H., Gu, Y.: ‘TCP with hop-oriented network coding in multi-radio multi-channel wireless mesh networks’, IET Netw., 2012, 1, (3), pp. 171–180 (doi: 10.1049/iet-net.2012.0048).
22. 22)
  - T. Ho , M. Medard . A random linear network coding approach to multicast. IEEE Trans. Inf. Theory , 4413 - 4430
23. 23)
  - 25. Kenniche, H.: ‘Random geometric graphs as model of wireless sensor networks’. Proc. Second Int. Conf. on Computer and Automation Engineering (ICCAE), Singapore, February 2010, pp. 103–107.
24. 24)
  - 13. Harvey, N., Kleinberg, R., Lehman, A.: ‘On the capacity of information networks’, IEEE Trans. Inf. Theory, 2006, 52, pp. 2345–2364 (doi: 10.1109/TIT.2006.874531).
25. 25)
  - 9. Yeung, R.W.: ‘Information Theory and Network Coding’ (Springer, New York, 2008).
26. 26)
  - 16. Koetter, R., Effros, M., Médard, M.: ‘A theory of network equivalence – part i: Point-to-point channel’, IEEE Trans. Inf. Theory, 2011, 57, pp. 972–995 (doi: 10.1109/TIT.2010.2102110).
27. 27)
  - R. Ahlswede , N. Cai , R. Li , R. Yeung . Network information flow. IEEE Trans. Inf. Theory , 1204 - 1216

Reduced functional dependence graphs

References

Related content