frequent_pattern_graph_miner.py

"""
FP-GraphMiner - A Fast Frequent Pattern Mining Algorithm for Network Graphs

A novel Frequent Pattern Graph Mining algorithm, FP-GraphMiner, that compactly
represents a set of network graphs as a Frequent Pattern Graph (or FP-Graph).
This graph can be used to efficiently mine frequent subgraphs including maximal
frequent subgraphs and maximum common subgraphs.

URL: https://www.researchgate.net/publication/235255851
"""

# fmt: off
edge_array= [
 ['ab-e1', 'ac-e3', 'ad-e5', 'bc-e4', 'bd-e2', 'be-e6', 'bh-e12', 'cd-e2', 'ce-e4',
'de-e1', 'df-e8', 'dg-e5', 'dh-e10', 'ef-e3', 'eg-e2', 'fg-e6', 'gh-e6', 'hi-e3'],
 ['ab-e1', 'ac-e3', 'ad-e5', 'bc-e4', 'bd-e2', 'be-e6', 'cd-e2', 'de-e1', 'df-e8',
'ef-e3', 'eg-e2', 'fg-e6'],
 ['ab-e1', 'ac-e3', 'bc-e4', 'bd-e2', 'de-e1', 'df-e8', 'dg-e5', 'ef-e3', 'eg-e2',
'eh-e12', 'fg-e6', 'fh-e10', 'gh-e6'],
 ['ab-e1', 'ac-e3', 'bc-e4', 'bd-e2', 'bh-e12', 'cd-e2', 'df-e8', 'dh-e10'],
 ['ab-e1', 'ac-e3', 'ad-e5', 'bc-e4', 'bd-e2', 'cd-e2', 'ce-e4', 'de-e1', 'df-e8',
'dg-e5', 'ef-e3', 'eg-e2', 'fg-e6']
]
# fmt: on


defget_distinct_edge(edge_array):
"""
 Return Distinct edges from edge array of multiple graphs
 >>> sorted(get_distinct_edge(edge_array))
 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
 """
distinct_edge=set()
forrowinedge_array:
foriteminrow:
distinct_edge.add(item[0])
returnlist(distinct_edge)


defget_bitcode(edge_array, distinct_edge):
"""
 Return bitcode of distinct_edge
 """
bitcode= ["0"] *len(edge_array)
fori, rowinenumerate(edge_array):
foriteminrow:
ifdistinct_edgeinitem[0]:
bitcode[i] ="1"
break
return"".join(bitcode)


defget_frequency_table(edge_array):
"""
 Returns Frequency Table
 """
distinct_edge=get_distinct_edge(edge_array)
frequency_table= {}

foritemindistinct_edge:
bit=get_bitcode(edge_array, item)
# print('bit',bit)
# bt=''.join(bit)
s=bit.count("1")
frequency_table[item] = [s, bit]
# Store [Distinct edge, WT(Bitcode), Bitcode] in descending order
sorted_frequency_table= [
 [k, v[0], v[1]]
fork, vinsorted(frequency_table.items(), key=lambdav: v[1][0], reverse=True)
 ]
returnsorted_frequency_table


defget_nodes(frequency_table):
"""
 Returns nodes
 format nodes={bitcode:edges that represent the bitcode}
 >>> get_nodes([['ab', 5, '11111'], ['ac', 5, '11111'], ['df', 5, '11111'],
 ... ['bd', 5, '11111'], ['bc', 5, '11111']])
 {'11111': ['ab', 'ac', 'df', 'bd', 'bc']}
 """
nodes= {}
for_, iteminenumerate(frequency_table):
nodes.setdefault(item[2], []).append(item[0])
returnnodes


defget_cluster(nodes):
"""
 Returns cluster
 format cluster:{WT(bitcode):nodes with same WT}
 """
cluster= {}
forkey, valueinnodes.items():
cluster.setdefault(key.count("1"), {})[key] =value
returncluster


defget_support(cluster):
"""
 Returns support
 >>> get_support({5: {'11111': ['ab', 'ac', 'df', 'bd', 'bc']},
 ... 4: {'11101': ['ef', 'eg', 'de', 'fg'], '11011': ['cd']},
 ... 3: {'11001': ['ad'], '10101': ['dg']},
 ... 2: {'10010': ['dh', 'bh'], '11000': ['be'], '10100': ['gh'],
 ... '10001': ['ce']},
 ... 1: {'00100': ['fh', 'eh'], '10000': ['hi']}})
 [100.0, 80.0, 60.0, 40.0, 20.0]
 """
return [i*100/len(cluster) foriincluster]


defprint_all() ->None:
print("\nNodes\n")
forkey, valueinnodes.items():
print(key, value)
print("\nSupport\n")
print(support)
print("\n Cluster \n")
forkey, valueinsorted(cluster.items(), reverse=True):
print(key, value)
print("\n Graph\n")
forkey, valueingraph.items():
print(key, value)
print("\n Edge List of Frequent subgraphs \n")
foredge_listinfreq_subgraph_edge_list:
print(edge_list)


defcreate_edge(nodes, graph, cluster, c1):
"""
 create edge between the nodes
 """
foriincluster[c1]:
count=0
c2=c1+1
whilec2<max(cluster.keys()):
forjincluster[c2]:
"""
 creates edge only if the condition satisfies
 """
ifint(i, 2) &int(j, 2) ==int(i, 2):
iftuple(nodes[i]) ingraph:
graph[tuple(nodes[i])].append(nodes[j])
else:
graph[tuple(nodes[i])] = [nodes[j]]
count+=1
ifcount==0:
c2=c2+1
else:
break


defconstruct_graph(cluster, nodes):
x=cluster[max(cluster.keys())]
cluster[max(cluster.keys()) +1] ="Header"
graph= {}
foriinx:
if (["Header"],) ingraph:
graph[(["Header"],)].append(x[i])
else:
graph[(["Header"],)] = [x[i]]
foriinx:
graph[(x[i],)] = [["Header"]]
i=1
whilei<max(cluster) -1:
create_edge(nodes, graph, cluster, i)
i=i+1
returngraph


defmy_dfs(graph, start, end, path=None):
"""
 find different DFS walk from given node to Header node
 """
path= (pathor []) + [start]
ifstart==end:
paths.append(path)
fornodeingraph[start]:
iftuple(node) notinpath:
my_dfs(graph, tuple(node), end, path)


deffind_freq_subgraph_given_support(s, cluster, graph):
"""
 find edges of multiple frequent subgraphs
 """
k=int(s/100* (len(cluster) -1))
foriincluster[k]:
my_dfs(graph, tuple(cluster[k][i]), (["Header"],))


deffreq_subgraphs_edge_list(paths):
"""
 returns Edge list for frequent subgraphs
 """
freq_sub_el= []
foredgesinpaths:
el= []
forjinrange(len(edges) -1):
temp=list(edges[j])
foreintemp:
edge= (e[0], e[1])
el.append(edge)
freq_sub_el.append(el)
returnfreq_sub_el


defpreprocess(edge_array):
"""
 Preprocess the edge array
 >>> preprocess([['ab-e1', 'ac-e3', 'ad-e5', 'bc-e4', 'bd-e2', 'be-e6', 'bh-e12',
 ... 'cd-e2', 'ce-e4', 'de-e1', 'df-e8', 'dg-e5', 'dh-e10', 'ef-e3',
 ... 'eg-e2', 'fg-e6', 'gh-e6', 'hi-e3']])

 """
foriinrange(len(edge_array)):
forjinrange(len(edge_array[i])):
t=edge_array[i][j].split("-")
edge_array[i][j] =t


if__name__=="__main__":
preprocess(edge_array)
frequency_table=get_frequency_table(edge_array)
nodes=get_nodes(frequency_table)
cluster=get_cluster(nodes)
support=get_support(cluster)
graph=construct_graph(cluster, nodes)
find_freq_subgraph_given_support(60, cluster, graph)
paths: list= []
freq_subgraph_edge_list=freq_subgraphs_edge_list(paths)
print_all()