2013 International Workshop on Nonlinear Circuits,Communications and Signal Processing
NCSP'13, Isrand of Hawaii, Hawaii, USA. March 4-7, 2013

Investigation of Associative Memory by Small World Hopfield
Neural Network with Characteristics of Social Network
Tomoya Shima, Chihiro Ikuta, Yoko Uwate and Yoshifumi Nishio
Tokushima University
2-1 Minami-Josanjima Tokushima 770-8506, JAPAN
Phone: +81-88-656-7470, Fax: +81-88-656-7471
E-mail: {s-tomoya, ikuta, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract
In the Hopfield Neural Network (HNN), each neuron is connected to every other neuron. Thereby, the HNN causes
high cost to generate the network in terms of implementation.
Small World Hopfield Neural Network (SWHNN) improves
ability for transmission by introducing the shortcut connections into the sparse regular network. However the storage
ability of the SWHNN decreases for associative memory because the SWHNN has sparse connectivity. In this study,
we propose the SWHNN with characteristic of Local Bridge(SWHNN-LB) using “local bridge”. And we explore performance of the SWHNN-LB using associative memory.
Figure 1: Example of the local bridge.
1. Introduction
Many researchers have developed artificial neural networkmodels. One of the network models is Hopfield Neural Network (HNN) [1], and the HNN intends to act as associativememory in this study. The HNN has full and symmetric connectivity and causes high cost to generate network in termsof implementation. A few years ago, Bohland et al. showedthat Small World HNN (SWHNN) [2] could be effective associative memory. The SWHNN is combined the HNN withthe small world network which has sparse connectivity andis one of social network [4] which is structure which showssocial relation, e.g. aerial line, infection with a virus, World
Wide Web and so on. The effective associative memory ofthe SWHNN comes from two properties of the small worldnetwork [3]. The small world network has high propagation
efficiency by two properties. First property results from introduction of regular network, and second property results froma few long range path which are called “shortcut”. However,the storage capability of the SWHNN is less than the conventional HNN by sparse connectivity. We believe that this problem can be solved if we apply the SWHNN to an importantcharacteristic in the real social network like the small world
network. In this study, we focus on “local bridge” which isfound by Granovetter [6] and is one of characteristics in social network. Example of the local bridge is shown in Fig. 1.

In Fig. 1, the shortest route from 1 to 25 is 1-25. Oneof second shortest route from 1 to 25 is 1-4-5-8-9-11-13-1415-16-20-22-23-25. The 1-25 route is predominantly shorter
than other routes. In this case, the 1-25 route is called thelocal bridge. Similarly, it is found that 8-9, 14-15, 15-16 and22-23 route are local bridge. In the social network, the local bridge affects the entire network in terms of propagationof information. Because the local bridge creates more andshorter routes. Thereby, the local bridge has greater influence on network if the second shortest route is longer. We
consider that the local bridge is similar to the shortcut of thesmall world network. If the shortcut has a similar property to
the local bridge, influence on network differs by shortcuts.
In this study, we propose the SWHNN with characteristics of Local Bridge (SWHNN-LB). In our proposed method,
we define “significance” of every shortcut based on theory of
the local bridge. Here, the significance is the second shortest
route length of two nodes which are connected by shortcut.
The determination method of the significance is based on theproperty of the local bridge. This property is that the localbridge has greater influence on network if the second shortest
route is longer. After that, we adjust the weight parameter ofshortcuts based on the significance and investigate influenceon network by different shortcuts of significance. We com-- 556 -pare our proposed method to the conventional SWHNN by for each shortcut. Here, the significance is the second shortexploring the network performance.
est route length of two nodes which are connected by shortcut. The determination method of the significance is basedon the property of the local bridge. This property is that the2. Small World Hopfield Neural Network Model [2]local bridge has greater influence on network if the second
shortest route is longer. Example of the significance is shown
In this study, we consider an one-dimensional ring modelin Fig 3. In this study, we define the significance of everyof the small world network. We start with a n-node ring regshortcut on the SWHNN. The method of adjustment is mulular lattice. Each unit in a n-node ring regular lattice is contiplied the weight parameters of each shortcut by α which isnected to its k nearest neighbors by edges. Here, the numberconstant. The SWHNN-LB is similarly used the HNN theory.
of k is very small compared to the number of n. Then, eachunit on the network is randomly rewired to other units withprobability p.
The small world network is quantified properties of the network structure by average route length L and clustering coefficient C. Here, the average route length L is measured theseparation between two nodes in the network, while the clustering coefficient C is measured the degree of cliquishness
connectivity in the network. Figure 2 shows L-C characteristic.
1

probability

0.8

Figure 3: Example of the SWHNN-LB (n = 16 and k = 4).

0.6
0.4
0.2
00.0001

4. HNN Working as Associative MemoryCL

0.001

0.01
p0.1

1Figure 2: L-C characteristic of SW, when n = 200 and k = 16.

The definition of the small world network model by Watts
is L ∼ Lrandom and C ≫ Crandom . From Fig 2, the definition of the small world network model is satisfied, when0.01 ≤ p ≤ 0.1. These properties result from introductionof a few long range path. It is known that a few long range
path are “shortcut”. Here, the shortcut connections are longer
than edges which connects each unit to its k nearest neighbors in this study. The SWHNN is combined the small worldnetwork like Fig. 2 with the HNN theory.

The HNN based on the model of biological neurons wasproposed by J.J. Hopfield in 1982 [1]. Every neurons in theHNN is connected to each other neuron in the network withno self-connection.
The HNN is used as the associative memory by exploiting the property that the network has multiple stable states.
Namely, if the parameters of the network can be decided insuch a way that the patterns to be stored become stable statesof the network, the network produces a stored pattern that issimilar to an input pattern. The process of the associativememory by the conventional HNN is described as follows.
[Step1 (HNN)]: If we apply the conventional HNN for theassociative memory, one pixel in an image corresponds withone neuron.
[Step2 (HNN)]: The HNN stores images by determining theweight parameter. The weight parameter is given by{3. Small World Hopfield Neural Network with Local
Bridge Model
We consider that the performance of the SWHNN improves by introducing the local bridge. In this study, we focus on the local bridge which is one of characteristic of thesocial network and important connection in terms of propagation of information in the real network. The introduction
method of the local bridge is that the significance is defined

wij =1P0∑P(p) (p)p=1 xi xj(i ̸= j)(i = j),(1)where P is the number of patterns, w is the weight parameterand x is the pattern of memory. It turns out that the weightparameter is symmetrical by Eq. (1).
[Step3 (HNN)]: The neurons is initialized by an unknown
image. Namely, the network is given the input. The state of- 557 -each neuron is determined by Eq. (2).

10.8

wij (t)xj (t),(2)recall rateui (t) =n∑
j=1

where u is the internal state of the neuron and x is the input
or output. The value of u is binary.
[Step4 (HNN)]: Neuron’s output is determined by a linearfunction. The equation of the determining Neuron’s output isgiven as follows.
xi (t + 1) ={ 1,−1,(ui (t) ≥ 0)
(ui (t) < 0).

(3)

0.6
0.4
0.2
010

15

20

2530

kFigure 5: Recall rate of each network depending on k, p = 0.1. (a) TheSWHNN. (b) The SWHNN-LB for the significance = 2 and α = 3.9. (c)The SWHNN-LB for the significance = 3 and α = 3.1. (d) The SWHNNLB for the significance = 4 and α = 3.1.

[Step5 (HNN)]: The HNN recalls a similar image to the input
image from the stored images by repeating Step4 to Step5.
On the other hand, the performance of the SWHNN-LB for
the significance 4 is as same as the SWHNN. From Fig. 5,
it is found that the performance of the SWHNN-LB differs
In this study, we apply three networks which are the by the significance. However, we expected that the SWHNNSWHNN and the SWHNN-LB to the associative memory. LB shows better performance if the significance becomes bigAnd, we compare recall rate of each network when k is ger. In order to examine this assumption, we explore existingchanged. In the computer simulations, we consider each net- probability of shortcuts of each significance in the SWHNNwork with 200 and 300 nodes. We prepare 3 stored binary LB. Figure 6 shows the existing probability.
patterns at random and 1 binary pattern to be input, which
differs from one stored pattern by 100%. Example of stored
1patterns is shown in Fig. 4. It is practically reasonable that a0.8
pattern within 1% error is considered as being recalled. We
randomly compose 25 each network. And, we define that the0.6
recall rate is the average of success rate of recall for each net0.4
work.
0.2
existing probability

5. Simulation Results023

4significanceFigure 6: The existing probability the SWHNN depending on the significance (k = 14).
Figure 4: Example of stored patterns.

From Figs. 5 and 6, it is found that the shortcuts for the significance 4 can not affect the network because the number ofthem is too small or nothing if k is more than 16. On the5.1 Network with 200 Nodes
other hand, the shortcuts for the significance 4 affect the netIn the case of each network with 200 nodes, the simula- work if k is 14. Thereby we assume that the SWHNN-LB
tion results are shown in Fig. 5. Figure 5 shows the recall depends on a number of the shortcuts of each significance.
rate when k is changed. The network (a) is the SWHNN. Furthermore, we explore the SWHNN-LB performance if weThe network (b), (c) or (d) are the SWHNN-LB for adjust- adjust the same number of the shortcuts of each significance.
ing shortcuts of the significance 2, 3 or 4 respectively. The Figure 7 shows the SWHNN-LB performance if we adjust
SWHNN-LB for the significance 2 and 3 show better recall 10 randomly-selected shortcuts of each significance in therate than the SWHNN. In particular, the SWHNN-LB for the SWHNN-LB. From Fig. 7, it is found that the SWHNN-LB
significance 3 shows better recall rate than the SWHNN to- shows better performance if the significance becomes bigger.
tally.

- 558 -1existing probability

recall rate

0.8
0.6
0.4
0.2
00.8
0.6
0.4
0.2
023significance4234significanceFigure 7: The SWHNN-LB performance for adjusting 10 randomlyselected shortcuts of each significance.

Figure 9: The existing probability the SWHNN depending on the significance (k = 14).

recall rate

5.2 Network with 300 Nodes
Figure 8 shows the simulation result for 300 nodes. If nodeof the SWHNN-LB increases, all networks show the better
recall rate than the SWHNN totally because the shortcuts forthe significance 4 in the SWHNN-LB increase by increasing
node.

0.6
0.50.40.30.20.10213sigificance4recall rate

0.8Figure 10: The SWHNN performance for adjusting 10 randomly-selectedshortcuts of each significance.

0.6
0.4
0.201015202530kFigure 8: Recall rate of each network depending on k, p = 0.1. (a) The
SWHNN. (b) The SWHNN-LB for the significance = 2 and α = 3.2. (c)The SWHNN-LB for the significance = 3 and α = 2.8. (d) The SWHNNLB for the significance = 4 and α = 3.2.

Furthermore, in the same way, we explore the existing probability of the shortcuts of each significance in the SWHNN-LB
and the SWHNN-LB performance if we adjust the same number of the shortcuts of each significance. Figures 9 and 10
show the existing probability and the SWHNN performance
respectively. From Fig. 10, it is found that the SWHNN-LB
shows better performance if the significance becomes bigger.
6. Conclusion
In this study, we have proposed the SWHNN-LB using
the local bridge which is the characteristic in the social network. And we have explored performance of the SWHNNLB using the associative memory. The computer simulation
results showed that the SWHNN-LB provided the better re-call performance than the SWHNN. Also, it was found that
the SWHNN-LB shows better performance if the significancebecomes bigger. Therefore, we showed that the part of characteristic of social network affects the propagation ability ofthe artificial network.
Acknowledgment
This work was partly supported by MEXT/JSPS Grant-in-Aidfor JSPS Fellows (24·10018).
References[1] J.J. Hopfield, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities,” Proceedings of the National
Academy of Sciences of the United States of America, vol. 79, pp. 25542558, 1982.
[2] J.W. Bohland and A.A. Minai, “Efficient Associative Memory Using
Small-World Architecture,” Neurocomputing, vol. 38-40, pp. 489-496,
2001.
[3] D. Watts and S. Strogatz, “Collective Dynamics of small-world’ networks,” Nature, vol. 393, pp. 440-442, 1998.
[4] S. Milgram, “The Small World Problem,” Psychology Today, vol. 2, pp.
60-67, 1967.
[5] D. Watts, “Small worlds : the dynamics of networks between order andrandomness,” Princeton University Press, 2003.
[6] S. Mark, “The Strength of Weak Ties”, Amerian Journal of Sociology,
vol 78, pp 1360-1380, 1973.

- 559 -