adjacency matrix to boolean matrix convert

I would like to ask if someone know how to convert a matrix based on number of contacts between nodes to a boolean matrix. With boolean matrix I would like to create a k-clique community. thanks for the answers

[Walter Roberson]

Please give us a sample input and desired boolean matrix.

[D N]

I have social matrix. this matrix show contacts between 10 nodes. node 1 and node 2 have 135.9167 contacts. This matrix l want convert with right threshhold into boolean matrix which I want use to k-clique algorith.

[Walter Roberson]

What would be the desired boolean matrix for the above social_matrix ? Is the task to find a threshold T, such that the adjacency matrix implied by social_matrix >= T, forms exactly k cliques, where k has been given ahead of time?

Could you post the matrix in numeric form?

[Walter Roberson]

https://en.wikipedia.org/wiki/Clique_problem

"In the k-clique problem, the input is an undirected graph and a number k, and the output is a clique of size k if one exists (or, sometimes, all cliques of size k)."

[D N]

yes I am looking for right value of threshold. I wrote a program where I take the max value in the social matrix and then I have loop for every 5% of max value (5% of max, 10% of max ... 100% max). In every loop I calculate the bool matrix so every value bigger than % of max in this loop is 1 otherwise is 0. then I calculate the quality in this bool matrix and write value in new vector. To the end of this loop I have a vector of all quality which I can do from social matrix. I take the best quality and this bool matrix I use to calculate the k-clique. I think that I lose some statistical data when I convert matrix with this method, because in every social matrix I have at least one number which is much more bigger than others.

[Walter Roberson]

What is "quality" for this purpose?

[D N]

quality will show me how good is the conenction between nodes and quality I calculate as you can see in code below:

 max = max(max(socialna_mat));% max value in social matrix
por_soc=1;
vektor_por_hodnot=zeros(1,20);
percenta=5;%value in percents;
while por_soc==1    
    porov_hodnota=max/100*percenta;
    bool_soc_mat=zeros(size(socialna_mat,2));
    for o=1:size(socialna_mat,2)
      for j=1:size(socialna_mat,2)
        if socialna_mat(o,j)>=porov_hodnota
            bool_soc_mat(o,j)=1;
        end
        if socialna_mat(o,j)<porov_hodnota
            bool_soc_mat(o,j)=0;
        end
       end
    end 

 m=sum(sum(socialna_mat))/2;
sum_ij=0;
for i=1:size(socialna_mat,2)
    for j=1:size(socialna_mat,2)
                    k_i=sum(socialna_mat(i,:));
                    k_j=sum(socialna_mat(:,j));
                    A_ij=socialna_mat(i,j);
                    sum_ij=sum_ij+(A_ij-(k_i*k_j)/(2*m))*bool_soc_mat(i,j);           
    end
end    
Q=1/(2*m)*sum_ij;

[Walter Roberson]

You can remove a couple of loops from that code. Your "for o" nested loop can be replaced by

bool_soc_mat = socialna_mat >= porov_hodnota;

By the way, please do not use "max" as the name of a variable, as that interferes with using it as the function max()

Answer 1

[Ahmet Cecen]

Sounds like what you want is simply:

 CliqueMatrix = AdjacencyMatrix >= Threshold;

Then you would sum along the columns and find if that value is bigger than your k:

 sum(CliqueMatrix) >= k

This would give you ones for nodes that are a member of a clique with at least size k.

[Walter Roberson]

That would not tell you which nodes were members of cliques: it would tell you which nodes have at least that many adjacent members.

The information can be used to help filter the possibilities, in that any node that does not have at least (k-1) adjacent vertices cannot be part of a clique of size k, since cliques are complete subgraphs.

This suggests a procedure to make the problem easier: calculate the degree for each graph, remove the nodes which do not have degree at least k-1. Repeat with the new graph, iterating until either the graph is empty (no cliques large enough) or every remaining node has at least k-1 neighbors. Now with the reduced set of vertices, proceed with the more difficult search.