Research on LFS Algorithm in Software Network


Betweenness centrality helps researcher to master the changes of the system from the overall perspective in software network. The existing betweenness centrality algorithm has high time complexity but low accuracy. Therefore, Layer First Searching (LFS) algorithm is proposed that is low in time complexity and high in accuracy. LFS algorithm searches the nodes with the shortest to the designated node, then travels all paths and calculates the nodes on the paths, at last get the times of each node being traveled which is betweenness centrality. The time complexity of LFS algorithm is O(V2).

Share and Cite:

W. Wang, H. Zhao, H. Li, J. Zhang, P. Li, Z. Liu, N. Guo, J. Zhu, B. Li, S. Yu, H. Liu and K. Yang, "Research on LFS Algorithm in Software Network," Journal of Software Engineering and Applications, Vol. 3 No. 2, 2010, pp. 185-189. doi: 10.4236/jsea.2010.32023.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] M. Pióro, A. Szentesi, J. Harmatos, A. Juttner, P. Ga-jowniczek, and S. Kozdrowski, “On open shortest path first related network optimization problems,” Perform-ance Evaluation, Vol. 48, pp. 201–223, May 2002.
[2] E. P. F. Chan and N. Zhang, “Finding shortest paths in large network systems,” Proceedings of the 9th ACM In-ternational Workshop on Advances in Geographic Infor-mation Systems (ACMGIS2001), Atlanta, Georgia, pp. 160–166, 2001.
[3] D. Awduchen, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao, “Overview and principles of internet traffic engi-neering,” RFC 3272, May 2002.
[4] D. Torrieri, “Algorithms for finding an optimal set of short disjoint paths in a communication network,” Com-munications, IEEE Transactions, Vol. 40, No. 11, pp. 1698–1702, 1992.
[5] B. Fortz and M. Thorup, “Internet traffic engineering by optimizing OSPF weights,” in Proceedings IEEE INFO-COM, pp. 519–528, 2000.
[6] X. Zhang, H. Zhao, W. B. Zhang, and C. Li, “Research on CFR algorithm for Internet,” Journal on Communications, Vol. 27, No. 9, September 2006.
[7] B. Fortz and M. Thorup, “Optimizing OSPF/IS-IS weights in a changing world,” IEEE Journal on Selected Areas in Communications, Vol. 20, No. 5, pp. 756–767, May 2002.
[8] G. Rétvári and T. Cinkler, “Practical OSPF traffic engi-neering,” IEEE Communications Letters, Vol. 8, No. 11, pp. 689–691, November 2004.
[9] A. R. Soltani, H. Tawfik, J. Y .Goulermas, et al., “Path planning in construction sites: Performance evaluation of the dijkstra, a* and GA search algorithms,” Advanced Engineering Informatics, Vol. 16, No. 4, pp. 291–303, 2002.
[10] Z. Wang, “Internet QoS: Architectures and mechanisms for quality of service,” Academic Press, CA, San Diego, 2001.
[11] M. Pióro and D. Medhi, “Routing, flow, and capacity design in communication and computer networks,” Mor-gan Kaufmann, CA, San Diego, November 2004.
[12] W. Ben-Ameur and E. Gourdin, “Internet routing and related topology issues,” SIAM Journal on Discrete Mathematics, Vol. 17, No. 1, pp. 18–49, 2003.
[13] Gamma Erich, Helm Richard, Johnson Ralph, and Vlis-sides John, “Design patterns: Elements of reusable ob-ject-oriented software,” Addison-Wesley Longman Pub-lishing Co., Inc. Boston, USA, 1995.
[14] M. M. Lehma and J. F. Rmail, “Software evolution and software evolution processes,” Annals of Software Engi-neering, Vol. 14, No. 1, pp. 275–309, 2002.
[15] B. Dougherty, J. White, C. Thompson, and D. C. Schmidt, “Automating hardware and software evolution analysis,” Engineering of Computer Based Systems (ECBS), 16th Annual IEEE International Conference and Workshop on the[C], pp. 265–274, 2009.
[16] S. N. Dorogovtsev and J. F. Mendes, “Scaling properties of scale-free evolving networks: Continuous approach,” Physical Review E, Vol. 63, No. 5, pp. 56125, 2001.
[17] N. Zhao, T. Li, L. L. Yang, Y. Yu, F. Dai, and W. Zhang, “The resource optimization of software evolution proc-esses,” Advanced Computer Control International Con-ference on [C] (ICACC), pp. 332–336, 2009.
[18] B. Behm, “Some future trends and implications for sys-tems and software engineering processes,” Systems En-gineering, Vol. 9, No. 1, pp. 1–19, 2006.
[19] Lollini Paolo, Bondavalli Andrea, and Di Giandomenico Felicita, “A decomposition-based modeling framework for complex systems,” IEEE Transaction on Reliability, Vol. 58, No. 1, pp. 20–33, 2009.
[20] Y. Ma and K. He, “A complexity metrics set for large-scale object-oriented software systems,” in Pro-ceedings of 6th International Conference on Computer and Information Technology, pp. 189–189, 2006.
[21] K. Madhavi and A. A. Rao, “A framework for visualizing model-driven software evolution,” IEEE International Advance Computing Conference (IACC), pp. 1628–1633, 2009.
[22] S. Valverde and R. V. Sole, “Network notifs in computa-tional graphs: A case study in software architecture,” Physical Review E, Vol. 72, No. 2, pp. 26107, 2005.

Copyright © 2022 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.