Analysis and Calculation of Odd Cycle Centrality Aimed for Vertex-Cover

作者：Wang, Ting^*; Wei, Wei

来源：International Conference on Electronic Science and Automation Control (ESAC), Zhengzhou, PEOPLES R CHINA, 2015-08-15 To 2015-08-16.

• centrality
• minimum vertex cover
• MAX-2-XORSAT
• random walk

We propose a kind of centrality, the odd cycle centrality which has strong relationship with solving minimum vertex-cover. The formal definition of the odd cycle centrality with its comparison to other centralities is given. Besides, as a variant of MAX-2-XORSAT, it is analyzed in the viewpoint of solving linear equations set. To calculate this centrality and view its effect on different graph structures, a random-walk based method is built to realize the centrality of each node on random graphs and scale-free networks. Using the importance order such as centrality provides one way to understand the topological structure or functions of a network, and it also offers a new viewpoint to solve the constraint satisfaction problems and recognize their complexity.

• 出版日期2015
• 单位北京航空航天大学