The chromatically uniqueness of bipartite graphs K （m, n） - A（]A] = 2） was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condi...The chromatically uniqueness of bipartite graphs K （m, n） - A（]A] = 2） was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condition guaranteeing that K（ m, n） - A （ I A ] = 2） is chromatically unique were obtained. This covers and improves the former correlative results.展开更多
With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleter...With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.展开更多
Many machine learning and data mining （MLDM] problems like recommendation, topic modeling, and medical diagnosis can be modeled as computing on bipartite graphs. However, inost distributed graph-parallel systems are ...Many machine learning and data mining （MLDM] problems like recommendation, topic modeling, and medical diagnosis can be modeled as computing on bipartite graphs. However, inost distributed graph-parallel systems are oblivious to the unique characteristics in such graphs and existing online graph partitioning algorithms usually cause excessive repli- cation of vertices as well as significant pressure on network communication. This article identifies the challenges and oppor- tunities of partitioning bipartite graphs for distributed MLDM processing and proposes BiGraph, a set of bipartite-oriented graph partitioning algorithms. BiGraph leverages observations such as the skewed distribution of vertices, discriminated computation load and imbalanced data sizes between the two subsets of vertices to derive a set of optimal graph partition- ing algorithms that result in minimal vertex replication and network communication. BiGraph has been implemented on PowerGraph and is shown to have a performance boost up to 17.75X （from 1.16X） for four typical MLDM algorithnls, due to reducing up to 80% vertex replication, and up to 96% network traffic.展开更多
基金Supported by the Natural Science Foundation of Jiangxi , China (No.0511006)
文摘The chromatically uniqueness of bipartite graphs K （m, n） - A（]A] = 2） was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condition guaranteeing that K（ m, n） - A （ I A ] = 2） is chromatically unique were obtained. This covers and improves the former correlative results.
基金Natural Science Foundation of Fujian, China (No.S0650011)
文摘With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.
基金This work was supported in part by the Doctoral Fund of Ministry of Education of China under Grant No. 20130073120040, the Program for New Century Excellent Talents in University of Ministry of Education of China, the Shanghai Science and Technology Developnmnt hinds under Grant No. 12QA1401700, a foundation for the Author of National Excellent Doctoral Dissertation of China, the Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing under Grant No. 2014A05, the National Natural Science Foundation of China under Grant Nos. 61003002, 61402284, the Shanghai Science and Technology Development Fund for High-Tech Achievement Translation under Grant No. 14511100902, and the Singapore National Research Foundation under Grant No. CREATE E2S2.
文摘Many machine learning and data mining （MLDM] problems like recommendation, topic modeling, and medical diagnosis can be modeled as computing on bipartite graphs. However, inost distributed graph-parallel systems are oblivious to the unique characteristics in such graphs and existing online graph partitioning algorithms usually cause excessive repli- cation of vertices as well as significant pressure on network communication. This article identifies the challenges and oppor- tunities of partitioning bipartite graphs for distributed MLDM processing and proposes BiGraph, a set of bipartite-oriented graph partitioning algorithms. BiGraph leverages observations such as the skewed distribution of vertices, discriminated computation load and imbalanced data sizes between the two subsets of vertices to derive a set of optimal graph partition- ing algorithms that result in minimal vertex replication and network communication. BiGraph has been implemented on PowerGraph and is shown to have a performance boost up to 17.75X （from 1.16X） for four typical MLDM algorithnls, due to reducing up to 80% vertex replication, and up to 96% network traffic.
