Network Modularity Optimisation in Prolog

Question

I am looking at network modularity optimisation in prolog.

I want to maximise Q where Q is the sum of the module scores for each module. A Module score is the number of edges in a module (Lm) divided by the number of edges in the network (L) minus the sum of the degrees of nodes in a module (Dm) divided by two times the number of edges in the network squared.

Modscore = (Lm/L) - (Dm/2L)^2

Q = sum(Modscores)

So each node to begin with is assigned a module randomly and then I want to output an optimum assignment of nodes to modules. Where there can be up to n modules. A edge is in a module if both its nodes are in the same module.

Is there a simple library or method to optimize a value like this in prolog? I have looked at : http://www.swi-prolog.org/man/clpfd.html but this does not seem appropriate as the value I wish to optimise is not an integer (but the assignment of nodes to modules is..). Is this right or am I mistaken?

Is this task not really suitable for prolog? I have made a Genetic Algorithm in python to solve this and I am aware of some other optimization algorithms and tool boxes in other languages. But I am interested in how easy or hard this is to do in prolog.

%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.

%%%Karate Graph%%%

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).

%%%Random Assignment to two modules%%%%

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).

Andrew Andrew · Accepted Answer · 2014-04-13T13:29:46

Very, very hard.

You are right that CLP could not be used to solve this as there is no appropriate domain. Each of the CLP solvers is tuned heavily using knowledge of the target domain and there is not one that can model arbitrary properties on a graph. It has been about five years since I last used SWI or Ciao for CLP, but I would be very surprised if this has changed as you are attempting to solve equations over the powerset of the graph vertices.

Raw Prolog would really suck for this, your heavy use of findall is necessary to determine transitive properties over a graph structure, but pretty much breaks the denotational semantics. Prolog works best at expressing declarative mappings between structures as complex as lists or trees. Graphs are slightly more complex than that as they cannot be expressed in a reference-free representation once they contain loops.

The other problem with Prolog is that it does not specify a solution-strategy other than brute force. If you want anything more sophisticated then you need to write a meta-interpreter. Once you go down that road if your solution strategy includes any kind of randomisation then you have to ask how you will generate random instances of the objects in your domain. Although treating module instances as integers allows simple generation the search bias is very weak and it leads to the question how will you improve on randomised blind search? On the other hand if you want to encode a stronger search bias then how can you generate random instances of your objects? Unless they have a canonical map to the integers this becomes very hard.

Network Modularity Optimisation in Prolog

1 Answers