-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathGraph Algorthms.mm
146 lines (137 loc) · 6.69 KB
/
Graph Algorthms.mm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
<map version="1.0.1">
<!-- To view this file, download free mind mapping software FreeMind from http://freemind.sourceforge.net -->
<node CREATED="1475338542629" ID="ID_357200752" MODIFIED="1475338642106" TEXT="Graph Algorthms">
<node CREATED="1475338644250" ID="ID_1708944394" MODIFIED="1475340052944" POSITION="right" TEXT="PageRank">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
The PageRank algorithm outputs a
<p>
<a title="Probability distribution" href="https://en.wikipedia.org/wiki/Probability_distribution">probability distribution</a> used to represent the likelihood that a person randomly clicking on links will arrive at any particular page. PageRank can be calculated for collections of documents of any size. It is assumed in several research papers that the distribution is evenly divided among all documents in the collection at the beginning of the computational process. The PageRank computations require several passes, called "iterations", through the collection to adjust approximate PageRank values to more closely reflect the theoretical true value.
</p>
<p>
https://en.wikipedia.org/wiki/PageRank
</p>
</body>
</html></richcontent>
<node CREATED="1475340520267" ID="ID_984642486" MODIFIED="1475340524720" TEXT="Applications">
<node CREATED="1475340540547" ID="ID_852507630" MODIFIED="1475340542137" TEXT="Biology">
<node CREATED="1475340542938" ID="ID_855935248" MODIFIED="1475340589444" TEXT="GeneRank ">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
<p>
span class="inline_editor_value">PageRank can be used to find out correlated genes by making use of the graph where nodes are the genes and edges are the known relationships between them. For example, a study highlighted 7 genes that better predicted the chances of survival of a patient with pancreatic ductal adenocarcinoma than all existing tools.
</p>
<p>
http://journals.plos.org/ploscompbiol/article?id=10.1371%2Fjournal.pcbi.1002511
</p>
</body>
</html></richcontent>
</node>
</node>
<node CREATED="1475340620295" ID="ID_1909889354" MODIFIED="1475340621666" TEXT="Engineering">
<node CREATED="1475340626602" ID="ID_454586938" MODIFIED="1475340677490" TEXT="MonitorRank">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
<p>
span class="inline_editor_value">It’s a tedious work to locate the root cause of an anomaly in a large service -oriented architecture. Given that an anomaly was detected in a system, MonitorRank solves a personalized PageRank problem on a weighted, augmented version of the call graph (Each combination of a service and a programming interface becomes a node in the MonitorRank graph. Edges are directed and indicate the direction of function calls e.g. web-page to photo store.), where the weights and augmentation depend on the anomaly detected. The localized PageRank scores help determine the anomaly.
</p>
<p>
http://dl.acm.org/citation.cfm?doid=2465529.2465753
</p>
</body>
</html></richcontent>
</node>
<node CREATED="1475340746340" ID="ID_1837534161" MODIFIED="1475340782297" TEXT="Linux Kernel ">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
<p>
A study focused on the functions in Linux determined the most important functions in the Linux kernel. In the graph under consideration, functions are nodes and function calls are edges. <i><nobr aria-hidden="true"><font face="STIXGeneral">printk</font></nobr></i>  amd <i><nobr aria-hidden="true"><font face="STIXGeneral">memset</font></nobr></i>turned out to be the important ones.
</p>
<p>
arxiv.org/abs/1003.5455
</p>
</body>
</html></richcontent>
</node>
</node>
<node CREATED="1475340844951" ID="ID_978041370" MODIFIED="1475341011774" TEXT="Sports">
<node CREATED="1475340867473" ID="ID_1211526974" MODIFIED="1475341119575" TEXT="Football">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
<p>
Prof. James Keener, in his brilliant article, ranked the American college football teams using many methods, one of which was a PageRank construction.
</p>
<p>
http://epubs.siam.org/doi/abs/10.1137/1035004
</p>
</body>
</html>
</richcontent>
</node>
<node CREATED="1475341121845" ID="ID_261616817" MODIFIED="1475341156925" TEXT="Tennis">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
<p>
A study on tennis players to find out the best player of all time using appropriate PaeRank construction placed Jimmy Connors in the best player position.
</p>
<p>
http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0017249
</p>
</body>
</html>
</richcontent>
</node>
</node>
<node CREATED="1475341284590" ID="ID_63530801" MODIFIED="1475341285995" TEXT="Literature">
<node CREATED="1475341290590" ID="ID_730098196" MODIFIED="1475341341641" TEXT="BookRank">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
<p>
Ever wondered what to read next? A study using PageRank algorithm made use of huge databases of books and related tags on social cataloging sites such as LibraryThing and Shelfari to produce eerily accurate suggestions for what to read next. In the network used, books were the nodes and tags were the edges.
</p>
<p>
http://cads.stanford.edu/projects/presentations/2009visit/bookrank.pdf
</p>
</body>
</html>
</richcontent>
</node>
</node>
<node CREATED="1475341353086" ID="ID_240148509" MODIFIED="1475341479523" TEXT="Recommender Systems">
<richcontent TYPE="NOTE"><html>
<head>
</head>
<body>
<p>
A recommender system attempts to predict what its users will do based on their past behavior. Netfix and Amazon have some of the most famous recommendation systems that predict movies and products, respectively, their users will enjoy. Localized PageRank helps to score potential predictions in many research studies on recommender systems.
</p>
<p>
<a href="http://www.aaai.org/Papers/IJCAI/2007/IJCAI07-444.pdf">http://www.aaai.org/Papers/IJCAI/2007/IJCAI07-444.pdf</a>
</p>
</body>
</html>
</richcontent>
</node>
</node>
</node>
<node CREATED="1475338652249" ID="ID_952066219" MODIFIED="1475338666099" POSITION="right" TEXT="Personalized PageRank"/>
<node CREATED="1475338686492" ID="ID_590648755" MODIFIED="1475338695587" POSITION="right" TEXT="Triangle Count"/>
<node CREATED="1475338696735" ID="ID_1755484628" MODIFIED="1475338709809" POSITION="right" TEXT="Shortest Paths"/>
<node CREATED="1475338712955" ID="ID_81424641" MODIFIED="1475338725721" POSITION="right" TEXT="Connected Components"/>
<node CREATED="1475338727283" ID="ID_828023907" MODIFIED="1475338737538" POSITION="right" TEXT="Label Propagation"/>
</node>
</map>