3
프롤로그에서 네트워크 모듈성 최적화를 검토 중입니다.프롤로그에서 네트워크 모듈화 최적화
Q를 최대화하고 싶습니다. Q는 각 모듈의 모듈 점수 합계입니다. 모듈 점수는 모듈의 가장자리 수 (Lm)를 네트워크의 가장자리 수 (L)에서 모듈의 노드 수 합계 (Dm)를 가장자리 수의 2 배로 나눈 값입니다. 네트워크 제곱.
Modscore = (LM/L) - (DM/2L)^2
Q = SUM (Modscores)
그래서로 시작하는 각각의 노드는 임의 모듈을 할당하고 I 출력하려는 모듈에 대한 노드의 최적 할당. 최대 n 개의 모듈이있을 수 있습니다. 노드가 모두 동일한 모듈에 있으면 에지가 모듈에 있습니다.
프롤로그에서 이와 같은 값을 최적화하는 간단한 라이브러리 또는 방법이 있습니까? 내가 봤어 : http://www.swi-prolog.org/man/clpfd.html하지만 이것은 최적의 값을 정수 (하지만 모듈에 노드의 할당 .. ..)되지 않으므로 적절하지 않는 것 같습니다. 이게 맞습니까? 아니면 제가 잘못 했습니까?
이 작업은 프롤로그에 적합하지 않습니까? 이 문제를 해결하기 위해 파이썬에서 유전자 알고리즘을 만들었으며 다른 언어의 다른 최적화 알고리즘과 도구 상자를 알고 있습니다. 그러나 이것이 프롤로그에서 얼마나 쉽고 까다로운 지에 관심이 있습니다.
%Modularity in prolog
%Undirected & unweighted
%not a multigraph
number_of_edges(L):-
findall(Edge_Id, edge(Edge_Id, X, Y), Edge_Ids), length(Edge_Ids, L).
edge_in_module(Edge_Id, Module):-
edge(Edge_Id, X, Y),
node_in_module(X, Module),
node_in_module(Y, Module).
edges_in_module(Edge_Ids, Module):-
bagof(Edge_Id, edge_in_module(Edge_Id,Module), Edge_Ids).
degree_of_node(Node, Degree):-
findall(Connected_Node,edge(_, Node, Connected_Node), Connected_Nodes), length(Connected_Nodes, OutDegree),
findall(Connected_Node2,edge(_, Connected_Node2, Node), Connected_Nodes2), length(Connected_Nodes2,InDegree),
Degree is InDegree + OutDegree.
degree_of_node_in_module(Node,Module,Degree):-
node_in_module(Node, Module),
degree_of_node(Node,Degree).
list_sum([Item], Item).
list_sum([Item1,Item2 | Tail], Total) :-
list_sum([Item1+Item2|Tail], Total).
mod_score(Module, Mod_score):-
findall(Degree, degree_of_node_in_module(Node,Module,Degree), Degrees),
list_sum(Degrees, Dm),
edges_in_module(Edges, Module),
length(Edges, Lm),
number_of_edges(L),
LmOverL is Lm/L,
DmOver2L is Dm/(2*L),
SecondTerm is DmOver2L*DmOver2L,
Mod_score is LmOverL- SecondTerm.
%%% 가라테 그래프 %%%
edge(edge1,node10,node3).
edge(edge2,node11,node1).
edge(edge3,node11,node5).
edge(edge4,node11,node6).
edge(edge5,node12,node1).
edge(edge6,node13,node1).
edge(edge7,node13,node4).
edge(edge8,node14,node1).
edge(edge9,node14,node2).
edge(edge10,node14,node3).
edge(edge11,node14,node4).
edge(edge12,node17,node6).
edge(edge13,node17,node7).
edge(edge14,node18,node1).
edge(edge15,node18,node2).
edge(edge16,node2,node1).
edge(edge17,node20,node1).
edge(edge18,node20,node2).
edge(edge19,node22,node1).
edge(edge20,node22,node2).
edge(edge21,node26,node24).
edge(edge22,node26,node25).
edge(edge23,node28,node24).
edge(edge24,node28,node25).
edge(edge25,node28,node3).
edge(edge26,node29,node3).
edge(edge27,node3,node1).
edge(edge28,node3,node2).
edge(edge29,node30,node24).
edge(edge30,node30,node27).
edge(edge31,node31,node2).
edge(edge32,node31,node9).
edge(edge33,node32,node1).
edge(edge34,node32,node25).
edge(edge35,node32,node26).
edge(edge36,node32,node29).
edge(edge37,node33,node15).
edge(edge38,node33,node16).
edge(edge39,node33,node19).
edge(edge40,node33,node21).
edge(edge41,node33,node23).
edge(edge42,node33,node24).
edge(edge43,node33,node3).
edge(edge44,node33,node30).
edge(edge45,node33,node31).
edge(edge46,node33,node32).
edge(edge47,node33,node9).
edge(edge48,node34,node10).
edge(edge49,node34,node14).
edge(edge50,node34,node15).
edge(edge51,node34,node16).
edge(edge52,node34,node19).
edge(edge53,node34,node20).
edge(edge54,node34,node21).
edge(edge55,node34,node23).
edge(edge56,node34,node24).
edge(edge57,node34,node27).
edge(edge58,node34,node28).
edge(edge59,node34,node29).
edge(edge60,node34,node30).
edge(edge61,node34,node31).
edge(edge62,node34,node32).
edge(edge63,node34,node33).
edge(edge64,node34,node9).
edge(edge65,node4,node1).
edge(edge66,node4,node2).
edge(edge67,node4,node3).
edge(edge68,node5,node1).
edge(edge69,node6,node1).
edge(edge70,node7,node1).
edge(edge71,node7,node5).
edge(edge72,node7,node6).
edge(edge73,node8,node1).
edge(edge74,node8,node2).
edge(edge75,node8,node3).
edge(edge76,node8,node4).
edge(edge77,node9,node1).
edge(edge78,node9,node3).
%%% 두 개의 모듈 %%%% 아주, 아주 열심히
node_in_module(node1,1).
node_in_module(node2,1).
node_in_module(node3,2).
node_in_module(node4,1).
node_in_module(node5,1).
node_in_module(node6,1).
node_in_module(node7,2).
node_in_module(node8,2).
node_in_module(node9,1).
node_in_module(node10,2).
node_in_module(node11,2).
node_in_module(node12,2).
node_in_module(node13,2).
node_in_module(node14,2).
node_in_module(node15,2).
node_in_module(node16,1).
node_in_module(node17,1).
node_in_module(node18,1).
node_in_module(node19,2).
node_in_module(node20,1).
node_in_module(node21,1).
node_in_module(node22,1).
node_in_module(node23,1).
node_in_module(node24,1).
node_in_module(node25,1).
node_in_module(node26,2).
node_in_module(node27,2).
node_in_module(node28,2).
node_in_module(node29,2).
node_in_module(node30,1).
node_in_module(node31,2).
node_in_module(node32,1).
node_in_module(node33,2).
node_in_module(node34,1).